Submission #682157

#	Time	Username	Problem	Language	Result	Execution time	Memory
682157		vjudge1	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	1356 ms	15220 KiB

xorsum

#include<bits/stdc++.h>
using namespace std;
const long long du=1e9+7;
const int maxn=1e3+9;
const int maxq=1e5+9;
long long a[maxn];
int l[maxq],r[maxq],x[maxq];
int b[maxn][maxn][3];
long long pw[maxq];
void update(int t,int x1,int y1,int x2,int y2){
if (x1>x2||y1>y2)return;
b[x1][y1][t]++;
b[x2+1][y1][t]--;
b[x1][y2+1][t]--;
b[x2+1][y2+1][t]++;
}
long long yoonjung(int p,int q){
if (p==0)return (q==0);
return (du+1)/2;
}
signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(nullptr);
	//freopen("usaco.INP","r",stdin);
	//freopen("usaco.ANS","w",stdout);
    int n;
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    int q;
    cin>>q;
    for (int i=1;i<=q;i++){
        cin>>l[i]>>r[i]>>x[i];
    }
    pw[0]=1;
    for (int i=1;i<=100000;i++)pw[i]=(pw[i-1]*2)%du;
    long long ans=0;
    for (int bit1=0;bit1<7;bit1++){
        for (int bit2=0;bit2<7;bit2++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                for (int k=0;k<3;k++){
                    b[i][j][k]=0;
                }
            }
        }
        for (int i=1;i<=q;i++){
            if ((x[i]>>bit1&1)&&(x[i]>>bit2&1)){
                update(0,l[i],l[i],r[i],r[i]);
                update(1,l[i],r[i]+1,r[i],n);
                update(2,1,l[i],l[i]-1,r[i]);
            }
            else if ((x[i]>>bit1&1)&&!(x[i]>>bit2&1)){
                update(1,l[i],l[i],r[i],n);
            }
            else if (!(x[i]>>bit1&1)&&(x[i]>>bit2&1)){
                update(2,1,l[i],r[i],r[i]);
            }
        }
        for (int j=1;j<=n;j++){
            for (int i=1;i<=n;i++){
                for (int k=0;k<3;k++){
                    b[i][j][k]+=b[i-1][j][k];
                }
            }
        }
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                for (int k=0;k<3;k++){
                    b[i][j][k]+=b[i][j-1][k];
                }
            }
        }
        for (int i=1;i<=n;i++){
            for (int j=i;j<=n;j++){
                long long bonus=(1<<bit1)*(1<<bit2)*i*(n-j+1);
                if (i!=j)bonus=(bonus*2)%du;
                for (int t1=0;t1<2;t1++){
                    for (int t2=0;t2<2;t2++){
                        for (int t3=0;t3<2;t3++){
                            int p1=((a[i]>>bit1&1)^t1^t2),p2=((a[j]>>bit2&1)^t1^t3);
                            if ((p1==1)&&(p2==1)){
                                long long newval=(bonus*pw[q])%du;
                                newval=(newval*yoonjung(b[i][j][0],t1))%du;
                                newval=(newval*yoonjung(b[i][j][1],t2))%du;
                                newval=(newval*yoonjung(b[i][j][2],t3))%du;
                                ans=(ans+newval)%du;
                            }
                        }
                    }
                }
            }
        }
        }
    }
    cout<<ans;
}

• 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