oj.uz

Submission #653506

# Submission time Handle Problem Language Result Execution time Memory
653506 2022-10-27T05:03:47 Z becaido Intergalactic ship (IZhO19_xorsum) C++17
26 / 100
 1148 ms 4300 KB 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

const int MOD = 1e9 + 7;
const int SIZE = 1005;
const int QSIZ = 1e5 + 5;

int n, q, ans;
int a[SIZE], pro[QSIZ];
int c1[SIZE], c2[SIZE], cnt[SIZE][SIZE];
tuple<int, int, int> ask[QSIZ];

inline pair<int, int> cal (int c) {
    if (c == 0) return {0, 1};
    return {pro[c - 1], pro[c - 1]};
}

void solve() {
    cin >> n;
    FOR (i, 1, n) cin >> a[i];
    pro[0] = 1;
    FOR (i, 1, max (n, 12)) pro[i] = (pro[i - 1] << 1) % MOD;
    cin >> q;
    FOR (i, 1, q) {
        auto &[l, r, x] = ask[i];
        cin >> l >> r >> x;
    }
    FOR (bi, 0, 6) FOR (bj, 0, 6) {
        fill (c1, c1 + n + 1, 0);
        fill (c2, c2 + n + 1, 0);
        FOR (i, 1, n) fill (cnt[i], cnt[i] + n + 1, 0);
        FOR (i, 1, q) {
            auto [l, r, x] = ask[i];
            if (x >> bi & 1) c1[l]++, c1[r + 1]--;
            if (x >> bj & 1) c2[l]++, c2[r + 1]--;
            if (x >> bi & 1 && x >> bj & 1) {
                cnt[l][l]++, cnt[l][r + 1]--;
                cnt[r + 1][l]--, cnt[r + 1][r + 1]++;
            }
        }
        FOR (i, 1, n) {
            c1[i] += c1[i - 1];
            c2[i] += c2[i - 1];
            FOR (j, 1, n) cnt[i][j] += cnt[i][j - 1];
            FOR (j, 1, n) cnt[i][j] += cnt[i - 1][j];
        }
        FOR (i, 1, n) FOR (j, 1, n) {
            auto [Odd, Even] = cal (cnt[i][j]);
            auto [odd1, even1] = cal (c1[i] - cnt[i][j]);
            auto [odd2, even2] = cal (c2[j] - cnt[i][j]);
            if (a[i] >> bi & 1) swap (odd1, even1);
            if (a[j] >> bj & 1) swap (odd2, even2);
            int val = (1ll * Odd * even1 % MOD * even2 + 1ll * Even * odd1 % MOD * odd2) % MOD;
            val = 1ll * val * pro[q - c1[i] - c2[j] + cnt[i][j]] % MOD;
            val = 1ll * val * min (i, j) % MOD * (n - max (i, j) + 1) % MOD;
            val = 1ll * pro[bi + bj] * val % MOD;
            ans = (ans + val) % MOD;
        }
    }
    cout << ans << '\n';
}

int main() {
    Waimai;
    solve();
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 12 ms 724 KB Output is correct
7 Correct 11 ms 724 KB Output is correct
8 Correct 12 ms 724 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 2656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1142 ms 4288 KB Output is correct
2 Correct 1132 ms 4284 KB Output is correct
3 Correct 1090 ms 4268 KB Output is correct
4 Correct 1148 ms 4300 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 476 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 476 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Incorrect 4 ms 512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 12 ms 724 KB Output is correct
7 Correct 11 ms 724 KB Output is correct
8 Correct 12 ms 724 KB Output is correct
9 Correct 2 ms 476 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Incorrect 12 ms 756 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 12 ms 724 KB Output is correct
7 Correct 11 ms 724 KB Output is correct
8 Correct 12 ms 724 KB Output is correct
9 Correct 2 ms 476 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Incorrect 4 ms 512 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 12 ms 724 KB Output is correct
7 Correct 11 ms 724 KB Output is correct
8 Correct 12 ms 724 KB Output is correct
9 Incorrect 62 ms 2656 KB Output isn't correct
10 Halted 0 ms 0 KB -