Submission #257346

#	Time	Username	Problem	Language	Result	Execution time	Memory
257346		BThero	Intergalactic ship (IZhO19_xorsum)	C++17	36 / 100	2094 ms	33400 KiB

xorsum

// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)1e3 + 5;
const int MAXQ = (int)1e5 + 5;
const int MOD = (int)1e9 + 7;

int mem[4][MAXN][MAXN];
int seg[4][MAXN][MAXN];
int pw[MAXQ], _pw[MAXQ];
array<int, 3> que[MAXN];
int dp[MAXQ][2];
int arr[MAXN];
int n, q, ans;

int addMod(int a, int b, int m = MOD) {
  a += b;
  
  if (m <= a) {
    a -= m;
  }
  
  return a;
}

int mulMod(int a, int b, int m = MOD) {
  return a * 1ll * b % m;
}

int binPow(int a, int b, int m = MOD) {
  int ret = 1;
  
  while (b > 0) {
    if (b & 1) {
      ret = mulMod(ret, a, m);
    }
    
    a = mulMod(a, a, m);
    b >>= 1;
  }
  
  return ret;
}

int bit(int x, int p) {
  return (x >> p) & 1;
}

void pre() {
  pw[0] = _pw[0] = 1;
  
  for (int i = 1; i < MAXQ; ++i) {
    pw[i] = mulMod(pw[i - 1], 2);
    _pw[i] = binPow(pw[i], MOD - 2);
  } 
  
  dp[0][0] = 1;
  
  for (int i = 1; i < MAXQ; ++i) {
    for (int j = 0; j < 2; ++j) {
      dp[i][j] = addMod(dp[i - 1][0], dp[i - 1][1]);
    }
  }
}

int calc(int p1, int p2) {
  int ret = 0;
  
  for (int i = 0; i < 4; ++i) {
    for (int l = 1; l <= n; ++l) {
      for (int r = 1; r <= n; ++r) {
        seg[i][l][r] = 0;
        mem[i][l][r] = 0;
      }
    }
  }
  
  for (int i = 1; i <= q; ++i) {
    auto &[l, r, x] = que[i];
    int msk = 0;
    
    if (bit(x, p1)) {
      msk |= 1;
    }
    
    if (bit(x, p2)) {
      msk |= 2;
    }
    
    seg[msk][l][r]++;
  }
  
  for (int i = 0; i < 4; ++i) {
    for (int l = 1; l <= n; ++l) {
      int cur = 0;
    
      for (int r = n; r; --r) {
        cur = addMod(cur, seg[i][l][r]);
        mem[i][l][r] = addMod(mem[i][l - 1][r], cur);
      }
    }
  }

  for (int a = 1; a <= n; ++a) {
    for (int b = 1; b <= n; ++b) {
      array<int, 4> cnt = {0, 0, 0, 0};
      int bitA = bit(arr[a], p1);
      int bitB = bit(arr[b], p2);
      
      //for (int msk = 0; msk < 4; ++msk) {
        //int X = mem[msk][a][a];
        //int Y = mem[msk][b][b];
        //int Z = mem[msk][min(a, b)][max(a, b)];
        //X -= Z;
        //Y -= Z;
        //int left = mem[msk][n][1] - X - Y - Z;
        
        //if (bit(msk, 0)) {
          //cnt[1] += X;
        //}
        //else {
          //cnt[0] += X;
        //}
        
        //if (bit(msk, 1)) {
          //cnt[2] += Y;
        //}
        //else {
          //cnt[0] += Y;
        //}
        
        //if (bit(msk, 0) && bit(msk, 1)) {
          //cnt[3] += Z;
        //}
        //else {
          //cnt[0] += Z;
        //}
        
        //cnt[0] += left;
      //}
    
      for (int i = 1; i <= q; ++i) {
        auto &[l, r, k] = que[i];
        int msk = 0;
        
        if (l <= a && a <= r && bit(k, p1)) {
          msk |= 1;
        }
        
        if (l <= b && b <= r && bit(k, p2)) {
          msk |= 2;
        }
        
        cnt[msk]++;
      }
      
      int cur = 0;
      
      for (int x = 0; x < 2; ++x) {
        for (int y = 0; y < 2; ++y) {
          for (int z = 0; z < 2; ++z) {
            if ((bitA ^ x ^ z) == 1 && (bitB ^ y ^ z) == 1) {
              int tmp = 1;
              tmp = mulMod(tmp, dp[cnt[1]][x]);
              tmp = mulMod(tmp, dp[cnt[2]][y]);
              tmp = mulMod(tmp, dp[cnt[3]][z]);
              cur = addMod(cur, tmp);
            }
          }
        }
      }
      
      cur = mulMod(cur, pw[cnt[0]]);
      cur = mulMod(cur, mulMod(min(a, b), n - max(a, b) + 1));
      ret = addMod(ret, cur);
    }
  }
  
  return ret;
}

void solve() {
  scanf("%d", &n);
  
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &arr[i]);
  }
  
  scanf("%d", &q);
  
  for (int i = 1; i <= q; ++i) {
    int l, r, x;
    scanf("%d %d %d", &l, &r, &x);
    que[i] = {l, r, x};
  }
  
  for (int a = 0; a < 7; ++a) {
    for (int b = 0; b < 7; ++b) {
      ans = addMod(ans, mulMod(calc(a, b), (1 << (a + b))));
    }
  }
  
  printf("%d\n", ans);
}

int main() {
  int tt = 1;
  pre();
  
  while (tt--) {
    solve();
  }

  return 0;
}

Compilation message (stderr)

xorsum.cpp: In function 'void solve()':
xorsum.cpp:196:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
xorsum.cpp:199:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &arr[i]);
     ~~~~~^~~~~~~~~~~~~~~
xorsum.cpp:202:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
xorsum.cpp:206:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &l, &r, &x);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9
• Subtask 5: 8 / 8
• Subtask 6: 0 / 11
• Subtask 7: 19 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8