제출 #1136530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136530		Hamed_Ghaffari	Intergalactic ship (IZhO19_xorsum)	C++20	100 / 100	619 ms	14096 KiB

xorsum

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")

using ll = long long;

#define pb push_back
#define SZ(x) int(x.size())

const int MXN = 1001;
const int MXQ = 2e5+1;
const int LOG = 7;
const int MOD = 1e9+7;

ll pw[MXQ], ans;
int n, q, a[MXN], L[MXQ], R[MXQ], X[MXQ], del[MXN], add[MXN][LOG];
vector<int> add2[MXN][LOG][LOG];

inline void fix(ll &x) { x -= (x>=MOD ? MOD : 0); }

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  pw[0] = 1;
  for(int i=1; i<MXQ; i++) fix(pw[i] = pw[i-1]<<1);
  cin >> n;
  for(int i=0; i<n; i++) cin >> a[i];
  cin >> q;
  for(int i=0; i<q; i++) {
    cin >> L[i] >> R[i] >> X[i]; L[i]--; R[i]--;
    for(int x=0; x<LOG; x++)
      if(X[i]>>x & 1) {
        add[L[i]][x]++;
        add[R[i]+1][x]--;
        for(int y=0; y<LOG; y++)
          if(X[i]>>y & 1)
            add2[L[i]][x][y].pb(i);
      }
  }
  for(int x=0; x<LOG; x++)
    for(int y=0; y<LOG; y++) {
      fill(del, del+n, 0);
      int A=0, B=0, C=0;
      for(int i=0; i<n; i++) {
        A += add[i][x];
        B += add[i][y];
        C += SZ(add2[i][x][y]) - del[i];
        for(int p : add2[i][x][y]) del[R[p]+1]++;
        int BB=B, CC=C;
        for(int j=i; j<n; j++) {
          if(i<j) {
            B += add[j][y];
            C -= del[j];
          }
          A -= C; B -= C;
          // 1 1
          fix(ans += 
          pw[q-A-B-C+(i<j)]
          *(i+1)%MOD
          *(n-j)%MOD
          *(A ? pw[A-1] : (a[i]>>x&1))%MOD
          *(B ? pw[B-1] : (a[j]>>y&1))%MOD
          *(C ? pw[C-1] : 1)%MOD
          *pw[x+y]%MOD);
          // 0 0
          fix(ans += 
          pw[q-A-B-C+(i<j)]
          *(i+1)%MOD
          *(n-j)%MOD
          *(A ? pw[A-1] : (a[i]>>x&1?0:1))%MOD
          *(B ? pw[B-1] : (a[j]>>y&1?0:1))%MOD
          *(C ? pw[C-1] : 0)%MOD
          *pw[x+y]%MOD);
          A += C; B += C;
        }
        B=BB, C=CC;
      }
    }
  cout << ans << '\n';
  return 0;
}

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