제출 #376280

#제출 시각아이디문제언어결과실행 시간메모리
376280ijxjdjdIntergalactic ship (IZhO19_xorsum)C++14
100 / 100
1717 ms6420 KiB
#include <bits/stdc++.h> #define FR(i, N) for (int i = 0; i < int(N); i++) #define all(x) begin(x), end(x) using namespace std; using ll = long long; const int MAXK = 7; const int MAXN = 1000 + 5; const int MAXQ = (int)(1e5) + 5; int flip[MAXN][MAXK]; int dblflip[MAXN][MAXK][MAXK]; int cur[MAXK][MAXK]; int mv[MAXK][MAXK]; bool arr[MAXN][MAXK]; vector<pair<int, int>> add[MAXN]; vector<pair<int, int>> rem[MAXN]; ll pows[MAXQ]; ll MOD = (int)(1e9) + 7; struct Query { int l, r, x; }; ll even(ll i) { if (i == 0) { return 1; } else { return pows[i-1]; } } ll odd(ll i) { if (i == 0) { return 0; } else { return pows[i-1]; } } ll mul(ll a, ll b) { return (a*b)%MOD; } ll sm2(int i, int j, vector<int>& a) { ll res = 0; for (int id = i; id <= j; id++) { res += a[id]; } return res*res; } ll sm(vector<int>& a) { ll res = 0; for (int i = 0; i < a.size(); i++) { for (int j = i; j < a.size(); j++) { res += sm2(i, j, a); } } return res; } ll fullCalc(vector<Query> q, vector<int> av) { ll res = 0; for (int i = 0; i < (1<<q.size()); i++) { vector<int> next(all(av)); for (int j = 0; j < q.size(); j++) { if ((1<<j)&i) { for (int k = q[j].l; k <= q[j].r; k++) { next[k] ^= q[j].x; } } } res += sm(next); } return res; } int main() { // freopen("input.in", "r", stdin); pows[0] = 1; for (int i = 1; i < MAXQ; i++) { pows[i] = 2*pows[i-1]; pows[i] %= MOD; } cin.tie(0); cin.sync_with_stdio(0); int N; cin >> N; vector<int> ori; vector<Query> q; for (int i = 0; i < N; i++) { int a; cin >> a; ori.push_back(a); for (int j = 0; j < MAXK; j++) { arr[i][j] = ((1<<j)&(a)); } } int Q; cin >> Q; // vector<pair<int, pair<int, int>>> vec; for (int i = 0; i < Q; i++) { int l, r, x; cin >> l >> r >> x; l--, r--; add[l].push_back({r, x}); q.push_back({l, r, x}); // vec.push_back({l, {r, x}});; for (int j = 0; j < MAXK; j++) { if ((1<<j)&x) { flip[l][j]++; flip[r+1][j]--; } } } // cout << fullCalc(q, ori) << '\n'; for (int i = 0; i < MAXK; i++) { for (int j = 1; j < N; j++) { flip[j][i] += flip[j-1][i]; } } ll res = 0; // for (int i = 0; i < N; i++) { // for (int j = 0; j < N; j++) { // for (int b1 = 0; b1 < MAXK; b1++) { // for (int b2 = 0; b2 < MAXK; b2++) { // ll X = 0; // ll Y = 0; // ll Z = 0; // for (auto& p : vec) { // if (p.first <= i && i <= p.first.first && ) { // X++; // } // else { // // } // } // } // } // } // } for (int i = 0; i < N; i++) { for (auto& p : add[i]) { for (int j = 0; j < MAXK; j++) { for (int k = 0; k < MAXK; k++) { if (((1<<j)&p.second) && ((1<<k)&p.second)) { cur[j][k]++; dblflip[p.first+1][j][k]--; } } } rem[p.first+1].push_back({i, p.second}); } for (auto& p : rem[i]) { for (int j = 0; j < MAXK; j++) { for (int k = 0; k < MAXK; k++) { if (((1<<j)&p.second) && ((1<<k)&p.second)) { cur[j][k]--; } } } } for (int j = 0; j < MAXK; j++) { for (int k = 0; k < MAXK; k++) { mv[j][k] = cur[j][k]; } } for (int j = i; j < N; j++) { if (j != i) { for (int b1 = 0; b1 < MAXK; b1++) { for (int b2 = 0; b2 < MAXK; b2++) { mv[b1][b2] += dblflip[j][b1][b2]; } } } for (int b1 = 0; b1 < MAXK; b1++) { for (int b2 = 0; b2 < MAXK; b2++) { int X = flip[i][b1]; int Z = flip[j][b2]; int Y = mv[b1][b2]; X -= Y; Z -= Y; if (arr[i][b1] && arr[j][b2]) { res += mul(i+1, N-j) * (i != j ? 2LL : 1LL)*mul(pows[Q-X-Y-Z], mul(pows[b1+b2], (mul(even(X), mul(even(Y), even(Z)))) + mul(odd(Y), mul(odd(X), odd(Z))))); } else if (!arr[i][b1] && arr[j][b2]) { res += mul(i+1, N-j) *(i != j ? 2LL : 1LL)*mul(pows[Q-X-Y-Z], mul(pows[b1+b2], (mul(odd(X), mul(even(Y), even(Z)))) + mul(odd(Y), mul(even(X), odd(Z))))); } else if (arr[i][b1] && !arr[j][b2]) { res += mul(i+1, N-j)*(i != j ? 2LL : 1LL) * mul(pows[Q-X-Y-Z], mul(pows[b1+b2], (mul(even(X), mul(even(Y), odd(Z)))) + mul(odd(Y), mul(odd(X), even(Z))))); } else { res += mul(i+1, N-j) * (i != j ? 2LL : 1LL) * mul(pows[Q-X-Y-Z], mul(pows[b1+b2], (mul(odd(X), mul(even(Y), odd(Z)))) + mul(odd(Y), mul(even(X), even(Z))))); } res %= MOD; } } } } cout << res << '\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

xorsum.cpp: In function 'll sm(std::vector<int>&)':
xorsum.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~
xorsum.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int j = i; j < a.size(); j++) {
      |                         ~~^~~~~~~~~~
xorsum.cpp: In function 'll fullCalc(std::vector<Query>, std::vector<int>)':
xorsum.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int j = 0; j < q.size(); j++) {
      |                         ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...