Codeforces Round #415 (Div. 1) C. Find a car

415-c.cpp

#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);
  }
}