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>
using namespace std;
typedef long long llint;
const int MAXN = 1005;
const int MAXQ = 200005;
const int MOD = 1000000007;
int n, q, ans;
llint sol[MAXQ];
int w[MAXN], lef[MAXQ], rig[MAXQ], val[MAXQ];
int cnt[MAXN][7], del[7][MAXN][7];
vector <int> v[MAXN], r[MAXN];
void precompute () {
int br[7];
memset(br, 0, sizeof br);
for (int i = 0; i < n; i++) {
for (auto q : v[i]) {
for (int j = 0; j < 7; j++) {
if (val[q] & (1 << j)) br[j]++;
}
}
for (int j = 0; j < 7; j++) cnt[i][j] = br[j];
for (auto q : r[i]) {
for (int j = 0; j < 7; j++) {
if (val[q] & (1 << j)) br[j]--;
}
}
}
}
void upd (int q, int k) {
for (int i = 0; i < 7; i++) {
if (!(val[q] & (1 << i))) continue;
for (int j = 0; j < 7; j++) {
if (val[q] & (1 << j)) del[i][lef[q]][j] += k;
}
}
}
void sweep () {
int br[7][7];
memset(br, 0, sizeof br);
for (int i = 0; i < n; i++) {
for (auto q : v[i]) upd(q, +1);
bool bta, btb;
for (int a = 0; a < 7; a++) {
bta = w[i] & (1 << a);
for (int j = 0; j <= i; j++) {
int d = (j + 1) * (n - i);
if (j < i) d *= 2;
for (int b = 0; b < 7; b++) {
br[a][b] += del[a][j][b];
btb = w[j] & (1 << b);
int samo_a = cnt[i][a] - br[a][b];
int samo_b = cnt[j][b] - br[a][b];
//cout << "bla " << i << " " << a << " " << j << " " << b << " " << samo_a << " " << samo_b << " " << br[a][b] << endl;
if (samo_a > 0 && samo_b > 0) {
sol[a + b + q - 2] += d;
} else if (samo_a == 0 && samo_b == 0) {
if (bta == btb) {
if (br[a][b] > 0) sol[a + b + q - 1] += d; else if (bta == 1) sol[a + b + q] += d;
}
} else if (samo_a == 0) {
if (br[a][b] > 0) sol[a + b + q - 2] += d; else if (bta == 1) sol[a + b + q - 1] += d;
} else {
if (br[a][b] > 0) sol[a + b + q - 2] += d; else if (btb == 1) sol[a + b + q - 1] += d;
}
}
}
}
for (auto q : r[i]) upd(q, -1);
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> w[i];
}
cin >> q;
for (int i = 0; i < q; i++) {
cin >> lef[i] >> rig[i] >> val[i];
lef[i] = 1; rig[i] = n; val[i] = (1 << 8) - 1;
lef[i]--; rig[i]--;
v[lef[i]].push_back(i);
r[rig[i]].push_back(i);
}
precompute();
sweep();
int pot = 1;
for (int i = 0; i < q + 20; i++) {
sol[i] %= MOD;
ans = (ans + (llint) pot * sol[i]) % MOD;
pot = pot * 2 % MOD;
}
cout << ans;
return 0;
}
# | 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... |