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>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef long long lint;
typedef pair<int,int> ii;
int arr[1005];
struct query{ int l, r, x; };
vector<query> queries;
bool in(int x, int bit){
return ((x & (1 << bit)) != 0);
}
lint mod = 1000000007;
lint two[100005];
lint ans = 0;
lint odd(int N){
if(N == 0) return 0;
else return two[N-1];
}
lint even(int N){
if(N == 0) return 1;
else return two[N-1];
}
void fix(lint &x){
x %= mod;
if(x < 0) x += mod;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
lint n; cin >> n;
for(int i = 1;i <= n;i++) cin >> arr[i];
int Q; cin >> Q;
for(int q = 0;q < Q;q++){
queries.push_back({});
query &QQ = queries.back();
cin >> QQ.l >> QQ.r >> QQ.x;
}
two[0] = 1;
for(int i = 1;i <= 100004;i++) two[i] = (two[i-1] * 2);
for(lint a = 1;a <= n;a++){
for(lint b = 1;b <= n;b++){
for(int aBit = 0;aBit < 7;aBit++){
for(int bBit = 0;bBit < 7;bBit++){
lint none = 0;
lint onlyA = 0;
lint onlyB = 0;
lint both = 0;
for(query q : queries){
bool A = false, B = false;
int l = q.l, r = q.r, x = q.x;
if(in(x, aBit) && l <= a && a <= r) A = true;
if(in(x, bBit) && l <= b && b <= r) B = true;
if(A && B) both++;
else if(A) onlyA++;
else if(B) onlyB++;
else none++;
}
//cout << a << " " << b << " " << aBit << " " << bBit << ": " << none << " " << onlyA << " " << onlyB << " " << both << "\n";
///don't use "both"
lint res = two[none] * two[aBit + bBit];
fix(res);
res *= min(a,b) * (n - max(a,b) + 1);
fix(res);
if(in(arr[a], aBit)) res *= even(onlyA);
else res *= odd(onlyA);
fix(res);
if(in(arr[b], bBit)) res *= even(onlyB);
else res *= odd(onlyB);
fix(res);
res *= even(both);
fix(res);
ans += res;
fix(ans);
//cout << res << " ";
///use "both"
res = two[none] * two[aBit + bBit];
fix(res);
res *= min(a,b) * (n - max(a,b) + 1);
fix(res);
if(in(arr[a], aBit)) res *= odd(onlyA);
else res *= even(onlyA);
fix(res);
if(in(arr[b], bBit)) res *= odd(onlyB);
else res *= even(onlyB);
fix(res);
res *= odd(both);
fix(res);
ans += res;
fix(ans);
}
}
}
}
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... |