oj.uz

답안 #331919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
331919 2020-11-30T17:47:48 Z keko37 Intergalactic ship (IZhO19_xorsum) C++14
0 / 100
 81 ms 4192 KB 
#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;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 78 ms 4192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -