제출 #376280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376280		ijxjdjd	Intergalactic ship (IZhO19_xorsum)	C++14	100 / 100	1717 ms	6420 KiB

xorsum

#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++) {
      |                         ~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 11 / 11
• Subtask 7: 19 / 19
• Subtask 8: 30 / 30
• Subtask 9: 8 / 8