Submission #675972

#TimeUsernameProblemLanguageResultExecution timeMemory
675972abcvuitunggioIntergalactic ship (IZhO19_xorsum)C++17
100 / 100
1319 ms27724 KiB
#include <iostream> #include <cstring> #define int long long using namespace std; const int mod=1000000007; int n,q,a[1001],dp[1010][1010][3],l[100001],r[100001],x[100001],pw=1,res; void update(int i, int j, int i2, int j2, int idx){ if (j>j2||i>i2) return; dp[i][j][idx]++; dp[i2+1][j][idx]--; dp[i][j2+1][idx]--; dp[i2+1][j2+1][idx]++; } int ch(int x, int y){ return (!x?!y:(mod+1)/2); } int32_t main(){ ios_base::sync_with_stdio(NULL);cin.tie(nullptr); cin >> n; for (int i=1;i<=n;i++) cin >> a[i]; cin >> q; for (int i=1;i<=q;i++){ cin >> l[i] >> r[i] >> x[i]; pw=pw*2%mod; } for (int i=0;i<7;i++){ for (int j=0;j<7;j++){ memset(dp,0,sizeof(dp)); for (int k=1;k<=q;k++) if ((x[k]>>i&1)&(x[k]>>j&1)){ update(l[k],l[k],r[k],r[k],0); update(l[k],r[k]+1,r[k],n,1); update(1,l[k],l[k]-1,r[k],2); } else if (x[k]>>i&1) update(l[k],1,r[k],n,1); else if (x[k]>>j&1) update(1,l[k],n,r[k],2); for (int x=1;x<=n;x++) for (int y=1;y<=n;y++) for (int k=0;k<3;k++) dp[x][y][k]+=dp[x][y-1][k]+dp[x-1][y][k]-dp[x-1][y-1][k]; for (int x=1;x<=n;x++) for (int y=x;y<=n;y++){ int val=(1<<(i+j))*min(x,y)*(n-max(x,y)+1)%mod; if (x<y) val=val*2%mod; int b=(a[x]>>i&1),c=(a[y]>>j&1); for (int t=0;t<2;t++) for (int t2=0;t2<2;t2++) for (int t3=0;t3<2;t3++) if ((b^t^t2)&(c^t^t3)) res=(res+val*pw%mod*ch(dp[x][y][0],t)%mod*ch(dp[x][y][1],t2)%mod*ch(dp[x][y][2],t3)%mod)%mod; } } } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...