제출 #342344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342344		kekw	Intergalactic ship (IZhO19_xorsum)	C++17	0 / 100	2068 ms	16488 KiB

xorsum

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define range(i, n) for (int i = 0; i < (n); ++i)
#define ar array
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()


typedef long long ll;
typedef long double ld;
using namespace std;

//using namespace __gnu_pbds;

const ll INF = 1e18 + 5;
const int INFi = 1e9;
const int maxN = 1e7 + 1500;
const int md2 = 998244353;
const int md = 1e9 + 7;


int add(int a, int b) {
    if (a + b >= md) return a + b - md;
    return a + b;
}

int sub(int a, int b) {
    if (a - b < 0) return a - b + md;
    return a - b;
}

int mul(int a, int b) {
    return (1ll * a * b) % md;
}

int binpow(int a, int b) {
    if (b <= 0) return 1;
    if (b % 2) return mul(a, binpow(a, b - 1));
    int m = binpow(a, b / 2);
    return mul(m, m);
}


int rev(int a) {
    return binpow(a, md - 2);
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    range(i, n) cin >> a[i];
    int q;
    cin >> q;
    vector<int> st2(q + 5);
    st2[0] = 1;
    for (int i = 1; i < st2.size(); ++i) st2[i] = mul(st2[i - 1], 2);
    vector<ar<int, 3>> b(q);
    range(i, q) range(j, 3) cin >> b[i][j];
    int ans = 0;
    sort(all(b));
    range(b1, 8) {
        range(b2, 8) {
            int result = 0;
            vector<vector<ar<int, 4>>> Cnt(n + 5, vector<ar<int, 4>>(n + 5));
            auto ADD = [&](int x1, int y1, int x2, int y2, int m) {
                Cnt[x1][y1][m] += 1;
                Cnt[x1][y1][0] -= 1;
                Cnt[x2 + 1][y2 + 1][m] += 1;
                Cnt[x2 + 1][y2 + 1][0] -= 1;
                Cnt[x1][y2 + 1][m] -= 1;
                Cnt[x2 + 1][y1][m] -= 1;
                Cnt[x1][y2 + 1][0] += 1;
                Cnt[x2 + 1][y1][0] += 1;
            };
            range(i, q) {
                auto[l, r, x] = b[i];
                Cnt[0][0][0]++;
                if ((x & (1 << b1)) && (x & (1 << b2))) {
                    ADD(l - 1, l - 1, r - 1, r - 1, 3);
                    ADD(l - 1, r, r - 1, n, 1);
                    if (l != 1) ADD(0, l - 1, l - 2, r - 1, 2);
                } else if (x & (1 << b1)) {
                    ADD(l - 1, 0, r - 1, n, 1);
                } else if (x & (1 << b2)) {
                    ADD(0, l - 1, n, r - 1, 2);
                }
            }
            range(i, n) {
                range(j, n) {
                    range(e, 4) {
                        if (i) Cnt[i][j][e] += Cnt[i - 1][j][e];
                        if (j) Cnt[i][j][e] += Cnt[i][j - 1][e];
                        if (i && j) Cnt[i][j][e] += Cnt[i - 1][j - 1][e];
                    }
                }
            }
            range(i, n) {
                for (int j = i; j < n; ++j) {
                    auto cnt = Cnt[i][j];
                    int cur = 0;
                    if (cnt[1] && cnt[2]) {
                        cur = st2[q - 2];
                    } else if (cnt[1] && cnt[3]) {
                        cur = st2[q - 2];
                    } else if (cnt[2] && cnt[3]) {
                        cur = st2[q - 2];
                    } else if (cnt[1]) {
                        if (a[j] & (1 << b2)) {
                            cur = st2[q - 1];
                        }
                    } else if (cnt[2]) {
                        if (a[i] & (1 << b1)) {
                            cur = st2[q - 1];
                        }
                    } else if (cnt[3]) {
                        int A = (a[i] >> b1) & 1;
                        int B = (a[j] >> b2) & 1;
                        if (A == B) {
                            cur = st2[q - 1];
                        }
                    } else if (((a[i] >> b1) & 1) && ((a[j] >> b2) & 1)) {
                        cur = st2[q];
                    }
                    result = add(result, mul(1 + (i != j), mul(cur, mul(i + 1, n - j))));
                }
            }
            ans = add(ans, mul(result, 1 << (b1 + b2)));
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(15) << fixed;
    int tests = 1;
    //cin >> tests;
    range(_, tests) {
        solve();
    }
    return 0;
}

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

xorsum.cpp: In function 'void solve()':
xorsum.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 1; i < st2.size(); ++i) st2[i] = mul(st2[i - 1], 2);
      |                     ~~^~~~~~~~~~~~

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