#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define fp(i,a,b) for(ll i=a ; i<b ; i++)
#define fn(i,a,b) for(int i=a ; i>=b ; i--)
#define ones(x) __builtin_popcount(x)
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define dbg(x) cout << (#x) << " = " << x << " "
#define fini cout << "\n";
#define line cout << "-----------------------------------\n";
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef tree<
ll,
null_type,
less_equal<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int read (){
int x = 0, f = 1; char s = getchar();while (s < '0' || s > '9') {if (s == '-') f = -1; s = getchar();}
while (s >= '0' && s <= '9') x = x * 10 + s - '0', s = getchar();
return x * f;
}
const ll M=1e5+7;
const ll N=1e3+7;
const ll inf=1e9;
const ll mod=1e9+7;
const ll mod2=998244353;
struct rng{
int l,r,x;
};
int n,q;
int a[N];
rng qs[M];
int c[N][N],c1[N],c2[N];
ll b[4],z[4];
ll e[M];
ll ans;
ll pro(ll a,ll b){
return (a*b)%mod;
}
void go(int ide){
cin >> n;
fp(i,1,n+1) cin >> a[i];
cin >> q;
fp(i,1,q+1) cin >> qs[i].l >> qs[i].r >> qs[i].x;
e[0] = 1;
fp(i,1,M) e[i] = (e[i-1]*2)%mod;
fp(k1,0,7) fp(k2,0,7){
fp(i,1,n+1){
fp(j,1,n+1) c[i][j] = 0;
c1[i] = c2[i] = 0;
}
fp(i,1,q+1){
int l = qs[i].l;
int r = qs[i].r;
if (1<<k1&qs[i].x) c1[l]++, c1[r+1]--;
if (1<<k2&qs[i].x) c2[l]++, c2[r+1]--;
if (((1<<k1)&(1<<k2))&qs[i].x){
c[l][l]++;
c[l][r+1]--;
c[r+1][l]--;
c[r+1][r+1]++;
}
}
fp(i,1,n+1){
c1[i] += c1[i-1];
c2[i] += c2[i-1];
fp(j,1,n+1) c[i][j] += c[i][j-1] + c[i-1][j] - c[i-1][j-1];
}
fp(i,1,n+1) fp(j,1,n+1){
z[3] = c[i][j];
z[2] = c1[i] - c[i][j];
z[1] = c2[j] - c[i][j];
z[0] = q - c1[i] - c2[j] + c[i][j];
fp(k,0,4) b[k] = 0;
b[2*(a[i]>>k1&1) + (a[j]>>k2&1)]++;
fp(k,0,4) b[k] = (b[k]*e[z[0]])%mod;
if (z[1]){
b[0] = b[1] = (e[z[1]-1]*(b[0] + b[1]))%mod;
b[2] = b[3] = (e[z[1]-1]*(b[2] + b[3]))%mod;
}
if (z[2]){
b[0] = b[2] = (e[z[2]-1]*(b[0]+b[2]))%mod;
b[1] = b[3] = (e[z[2]-1]*(b[1]+b[3]))%mod;
}
if (z[3]){
b[0] = b[3] = (e[z[3]-1]*(b[0]+b[3]))%mod;
b[1] = b[2] = (e[z[3]-1]*(b[1]+b[2]))%mod;
}
ans = (ans + pro(e[k1+k2], pro(pro(min(i,j), n-max(i,j)+1), b[3])))%mod;
// dbg(ans); fini;
}
// line;
}
cout << ans << "\n";
}
int main(){
fastio;
int tst=1;
// cin >> tst;
// cout << fixed << setprecision(12);
fp(i,0,tst) go(i+1);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
30 ms |
1620 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
1520 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1891 ms |
5052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
