Submission #1187486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187486		PieArmy	Intergalactic ship (IZhO19_xorsum)	C++20	100 / 100	882 ms	3184 KiB

xorsum

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

int n,q;
int arr[1023];
int lef[100023],rig[100023],k[100023];
int pref[1023][7],s[1023];
ll two[100023];
vector<int>v[1023];
const ll MOD=1e9+7;
ll ans=0;

ll carp(ll x,ll y){
	if(x>=MOD)x%=MOD;
	if(y>=MOD)y%=MOD;
	return (x*y)%MOD;
}

ll topla(ll x,ll y){
	if(x+y<MOD)return x+y;
	return (x+y)%MOD;
}

ll cal(int a,int b,int x,int y){
	if(a==0&&x==0)return 0;
	if(b==0&&y==0)return 0;
	ll res=1;
	if(a)res=carp(res,two[a-1]);
	if(b)res=carp(res,two[b-1]);
	return res;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	cin>>q;
	two[0]=1;
	for(int i=1;i<=q;i++){
		two[i]=(two[i-1]*2)%MOD;
		cin>>lef[i]>>rig[i]>>k[i];
		v[lef[i]].pb(i);
		for(int j=0;j<7;j++){
			if(!((1<<j)&k[i]))continue;
			pref[lef[i]][j]++;
			pref[rig[i]+1][j]--;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<7;j++){
			pref[i][j]+=pref[i-1][j];
		}
	}
	for(int b1=0;b1<7;b1++){
		for(int b2=0;b2<7;b2++){
			int both=0;
			for(int i=1;i<=n;i++){
				for(int x:v[i]){
					if((k[x]&(1<<b1))==0)continue;
					if((k[x]&(1<<b2))==0)continue;
					s[rig[x]+1]++;
					both++;
				}
				both-=s[i];
				s[i]=0;
				int both2=both;
				for(int j=i;j<=n;j++){
					both-=s[j];
					int x=(1<<b1)&arr[i],y=(1<<b2)&arr[j];
					ll res=carp(carp(carp(i,n-j+1),1+!!(j-i)),carp(two[q-pref[i][b1]-pref[j][b2]+both],carp(1<<b1,1<<b2)));
					if((x==0&&pref[i][b1]+both==0)||(y==0&&pref[j][b2]+both==0))continue;
					if((!!x)!=(!!y)&&x+y==0)continue;
					if(both)ans=topla(ans,carp(res,carp(topla(cal(pref[i][b1]-both,pref[j][b2]-both,!!x,!!y),cal(pref[i][b1]-both,pref[j][b2]-both,!x,!y)),two[both-1])));
					else ans=topla(ans,carp(res,cal(pref[i][b1]-both,pref[j][b2]-both,!!x,!!y)));
				}
				both=both2;
			}
		}
	}
	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