This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize ("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1002+ 10 , maxq = 1e6+10 , lg = 18 , inf= 1e9 , mod = 1e9+7 ;
int t[maxn] ,prt[maxn] , f[maxn][9] , pr[maxn][8] , a2[maxq] , pr2[maxn][8] , a[maxn];
struct bz{
int l , r , w ;
};
bz b[maxn] ;
vector <int> L[maxn] , R[maxn] ;
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
a2[0] = 1;
rep(i , 1, maxq-1){
a2[i] = a2[i-1] * 2 % mod ;
}
int n ;cin >> n;
rep(i , 1, n){
cin >> a[i] ;
}
int Q ;
cin >> Q;
rep(i , 1, Q){
cin >> b[i].l >> b[i].r >> b[i].w;
L[b[i].l].pb(i);
R[b[i].r].pb(i) ;
rep(j , 0 , 6){
pr2[b[i].l][j] += (b[i].w>>j&1) ;
pr2[b[i].r+1][j] -= (b[i].w>>j&1) ;
}
}
rep(i , 1, n){
rep(j , 0 , 6){
pr2[i][j] += pr2[i-1][j] ;
}
}
int ans =0 ;
rep(k , 0 , 6){
rep(i , 1 , n){
for(int id : L[i]){
if((b[id].w>>k&1) == 0)continue ;
rep(z , 0 , 6){
f[b[id].r][z] += (b[id].w>>z&1) ;
}
}
rep(z , 0 , 6){
int sm= 0 ;
per(j , n, i){
sm += f[j][z] ;
int o[2][2] ;
o[1][1] = sm ;
o[1][0] = pr2[i][k] - sm;
o[0][1] = pr2[j][z] - sm ;
o[0][0] = Q - o[0][1] - o[1][0] - o[1][1] ;
int Z = i * (n-j+1) % mod * (1ll<<k) %mod * (1ll<<z)%mod;
if(i != j)Z = Z * 2 % mod ;
// if(k==6 && z==6){
// cout << o[0][0] << " "<< o[1][0] << " " << o[0][1] << " " << o[1][1] << " " << Z << " " << a2[Q] << " " <<((a[i]>>k&1) && (a[j]>>z&1))<< "<--\n";
// }
if((o[1][1]!=0)+(o[1][0]!=0)+(o[0][1]!=0) >= 2){
ans = (ans + Z * a2[Q-2] % mod)%mod ;
}else if((o[1][1]!=0)+(o[1][0]!=0)+(o[0][1]!=0) == 0){
if((a[i]>>k&1) && (a[j]>>z&1))ans = (ans + Z * a2[Q])%mod;
}else{
int x1 = 1 , y1 =1 ;
if(o[0][1] != 0)x1 = 0;
if(o[1][0] != 0)y1 = 0 ;
if(((a[i]>>k&1)) && (a[j]>>z&1))ans = (ans + Z * a2[Q-1]) % mod ;
if(((a[i]>>k&1)^(x1==1)) && ((a[j]>>z&1)^(y1==1)))ans = (ans + Z * a2[Q-1]) % mod ;
}
}
}
}
rep(i , 0 , n){
rep(j , 0 , 6){
f[i][j] = 0;
}
}
}
cout << ans << "\n";
}
/*
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |