#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<=i;k++){
int z=1;
if(i!=k){
z=2;
}
int a=ct[i][k],b=pre[j][l][i]-a,c=pre[j][l][k]-a;
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)&(a==0));
u+=((b==0)&(c==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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
7468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
351 ms |
5016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
