Submission #651280

#	Time	Username	Problem	Language	Result	Execution time	Memory
651280		alvingogo	Intergalactic ship (IZhO19_xorsum)	C++14	100 / 100	1395 ms	18220 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=8;
	vector<vector<int> > pre(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][l]++;
				if(r+1<n){
					pre[j][r+1]--;
				}
			}
		}
	}
	int ans=0;
	for(int j=0;j<A;j++){
		for(int i=1;i<n;i++){
			pre[j][i]+=pre[j][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<=i;k++){
					int z=1;
					if(i!=k){
						z=2;
					}
					int a=ct[i][k],b=pre[j][i]-a,c=pre[l][k]-a;
					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;
						}
						now=mul(now,p2[max(a-1,0)]);
						if(h==1){
							x^=1;
							y^=1;
						}
						if(x==0 && b==0){
							now=0;
						}
						if(y==0 && c==0){
							now=0;
						}
						now=mul(now,mul(p2[max(b-1,0)],p2[max(c-1,0)]));
						add(ans,mul(z,mul(mul(now,p2[j+l]),mul(k+1,n-i))));
						if(now!=0){
							//cout << l << " " << j << " " << k << " " << i << " " << a << " " << c << " " << b << " " << now << " " << mul(z,mul(mul(now,p2[j+l]),mul(k+1,n-i))) << endl;
						}
						now=p2[q-a-b-c];
					}
				}
			}
		}
	}
	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