Skip to content

Instantly share code, notes, and snippets.

@potetisensei
Created May 21, 2017 08:50
Show Gist options
  • Save potetisensei/7d03618b13d21f75643d27e65bf08238 to your computer and use it in GitHub Desktop.
Save potetisensei/7d03618b13d21f75643d27e65bf08238 to your computer and use it in GitHub Desktop.
Codeforces Round #415 (Div. 1) C. Find a car
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long int LLI;
#define L 0
#define H 1
#define W 2
#define HW 3
#define LEFT 0
#define MAXNUM 1
int q;
LLI x1;
LLI my1;
LLI x2;
LLI y2;
LLI k;
LLI allowed[32];
LLI width[32];
LLI height[32];
LLI dp[32][2][4];
LLI num[32][2][4];
bool exist[32][2][4];
LLI calc(int x, int y) {
if (x == 0 || y == 0) return 0;
int t = max(x, y);
int cnt = 1;
while (t > 0) {
cnt++;
t /= 2;
}
LLI k_ = k;
int cnt2 = 1;
while (1) {
k_ = k_%2 ? (k_+1)/2 : k_/2;
cnt2++;
if (k_ == 1) break;
}
cnt = max(cnt, cnt2);
width[cnt-1] = x;
height[cnt-1] = y;
allowed[cnt-1] = k;
for (int i=cnt-2; i>=0; i--) {
allowed[i] = allowed[i+1]%2 ? (allowed[i+1]+1)/2 : allowed[i+1]/2;
width[i] = width[i+1]/2 + width[i+1]%2;
height[i] = height[i+1]/2 + height[i+1]%2;
}
fill(num[0][0], num[cnt][0], 0);
fill(dp[0][0], dp[cnt][0], 0);
fill(exist[0][0], exist[cnt][0], false);
num[0][MAXNUM][HW] = 1;
dp[0][MAXNUM][HW] = 1;
exist[0][MAXNUM][HW] = true;
for (int i=0; i<cnt-1; i++) {
for (int j=0; j<2; j++) {
for (int k=0; k<4; k++) {
if (!exist[i][j][k]) continue;
for (int s=0; s<2; s++) {
for (int t=0; t<2; t++) {
LLI p = (s+t)%2;
LLI v = (MOD + ((dp[i][j][k]*2+(p-1)*num[i][j][k])%MOD))%MOD;
LLI n = num[i][j][k];
if (j == MAXNUM && p && allowed[i]*2 > allowed[i+1]) continue;
if ((k&W) && s && width[i]*2 > width[i+1]) continue;
if ((k&H) && t && height[i]*2 > height[i+1]) continue;
int nj = LEFT;
if (j == MAXNUM && allowed[i]*2-1+p == allowed[i+1]) nj = MAXNUM;
int nk = L;
if ((k&H) && height[i]*2-1+t == height[i+1]) nk += H;
if ((k&W) && width[i]*2-1+s == width[i+1]) nk += W;
exist[i+1][nj][nk] = true;
dp[i+1][nj][nk] = (dp[i+1][nj][nk]+v)%MOD;
num[i+1][nj][nk] = (num[i+1][nj][nk]+n)%MOD;
}
}
}
}
}
LLI ret = 0;
for (int i=0; i<4; i++) {
ret += dp[cnt-1][LEFT][i];
ret += dp[cnt-1][MAXNUM][i];
ret %= MOD;
}
return ret;
}
int main() {
scanf("%d", &q);
while (q--) {
scanf("%lld%lld%lld%lld%lld", &x1, &my1, &x2, &y2, &k);
LLI ans = calc(x2, y2) - calc(x2, my1-1) - calc(x1-1, y2) + calc(x1-1, my1-1);
printf("%lld\n", (MOD+ans%MOD)%MOD);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment