Submission #651260

#	Time	Username	Problem	Language	Result	Execution time	Memory
651260		alvingogo	Intergalactic ship (IZhO19_xorsum)	C++14	0 / 100	1127 ms	7524 KiB

xorsum

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct BIT{
	int n;
	vector<int> bt;
	void init(int x){
		n=x;
		bt.resize(n+1);
	}
	void update(int x,int y){
		x++;
		for(;x<=n;x+=(x&-x)){
			bt[x]+=y;
		}
	}
	int query(int x){
		x++;
		int ans=0;
		for(;x>0;x-=(x&-x)){
			ans+=bt[x];
		}
		return ans;
	}
};
const int mod=1e9+7;
void add(int& x,int y){
	x+=y;
	x-=mod*(x>=mod);
}
int mul(int x,int y){
	return 1ll*x*y%mod;
}
int po(int x,int y){
	int z=1;
	while(y){
		if(y&1){
			z=mul(z,x);
		}
		x=mul(x,x);
		y>>=1;
	}
	return z;
}
int main(){
    AquA;
	vector<int> p2(1e5+7);
	p2[0]=1;
	for(int i=1;i<100007;i++){
		p2[i]=mul(p2[i-1],2);
	}
	int n;
	cin >> n;
	vector<int> v(n);
	for(int i=0;i<n;i++){
		cin >> v[i];
	}
	int q;
	cin >> q;
	const int A=7;
	vector<vector<vector<int> > > pre(A,vector<vector<int> >(A,vector<int>(n)));
	vector<vector<vector<pair<int,int> > > > vq(A,vector<vector<pair<int,int> > >(A));
	for(int i=0;i<q;i++){
		int l,r,x;
		cin >> l >> r >> x;
		l--;
		r--;
		for(int j=0;j<A;j++){
			if((x>>j)&1){
				for(int k=0;k<A;k++){
					if((x>>k)&1){
						vq[j][k].push_back({l,r});
						pre[j][k][l]++;
						if(r+1<n){
							pre[j][k][r+1]--;
						}
					}
				}
			}
		}
	}
	int ans=0;
	for(int j=0;j<A;j++){
		for(int k=0;k<A;k++){
			for(int i=1;i<n;i++){
				pre[j][k][i]+=pre[j][k][i-1];
			}
		}
	}
	for(int j=0;j<A;j++){
		for(int l=0;l<A;l++){
			BIT bt;
			bt.init(n);
			vector<vector<int> > ct(n,vector<int>(n));
			sort(vq[j][l].begin(),vq[j][l].end(),[&](pair<int,int> a,pair<int,int> b){return a.sc<b.sc;});
			int ll=0;
			for(auto h:vq[j][l]){
				bt.update(h.fs,1);
			}
			for(int i=0;i<n;i++){
				for(int k=0;k<=i;k++){
					ct[i][k]=bt.query(k);
				}
				while(ll<(int)vq[j][l].size() && vq[j][l][ll].sc==i){
					bt.update(vq[j][l][ll].fs,-1);
					ll++;
				}	
			}
			for(int i=0;i<n;i++){
				for(int k=0;k<n;k++){
					int z=1;
					if(i!=k){
						z=1;
					}
					int a=ct[i][k],b=pre[j][l][i]-a,c=pre[j][l][k]-a;
					assert(b>=0 && c>=0);
					int now=p2[q-a-b-c];
					int x=(v[i]>>j)&1,y=(v[k]>>l)&1;
					for(int h=0;h<2;h++){
						if(h==1 && a==0){
							continue;
						}
						if(a==0){
							now=mul(now,p2[a]);
						}
						else{
							now=mul(now,p2[a-1]);
						}
						if(h==1){
							x^=1;
							y^=1;
						}
						if(x==0 && b==0){
							now=0;
						}
						if(y==0 && c==0){
							now=0;
						}
						if(b==0){
							now=mul(now,p2[b]);
						}
						else{
							now=mul(now,p2[b-1]);
						}
						if(c==0){
							now=mul(now,p2[c]);
						}
						else{
							now=mul(now,p2[c-1]);
						}
						add(ans,mul(z,mul(mul(now,p2[j+l]),mul(min(i,k)+1,n-max(i,k)))));
						if(now!=0){
							//cout << j << " " << l << " " << i << " " << k << " " << mul(z,mul(mul(now,p2[j+l]),mul(k+1,n-i))) << "\n";
						}
						now=p2[q-a-b-c];
					}
					/*
					if(b==0 && c==0){
						if(((((v[i]>>j)&1) xor ((v[k]>>l)&1)))==1){
							continue;
						}
						if(a==0 && ((v[i]>>j)&1)==0){
							continue;
						}
						else{
							if(a==0){
								add(ans,mul(z,mul(mul(p2[max(q,0)],p2[l+j]),mul(k+1,n-i))));
							}
							else{
								add(ans,mul(z,mul(mul(p2[max(q-1,0)],p2[l+j]),mul(k+1,n-i))));
							}
							continue;
						}
					}
					if(pre[j][l][i]==0 && ((v[i]>>j)&1)==0){
						continue;
					}
					if(pre[j][l][k]==0 && ((v[k]>>l)&1)==0){
						continue;
					}
					int u=((b==0)&(c==0));
					u+=(a==0);
					add(ans,mul(p2[u],mul(z,mul(mul(p2[max(q-2,0)],p2[l+j]),mul(k+1,n-i)))));
					*/
				}
			}
		}
	}
	cout << ans << "\n";
    return 0;
}

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