oj.uz

Submission #426658

# Submission time Handle Problem Language Result Execution time Memory
426658 2021-06-14T08:46:46 Z palilo 즐거운 사진 수집 (JOI13_collecting) C++17
0 / 100
 1289 ms 62332 KB 
#include <bits/stdc++.h>
using namespace std;

class segtree {
    const int n;
    vector<int> tree, cnt;

public:
    segtree(int _n) : n(_n), tree(1 << (n + 1)), cnt(n) {
        for (int i = 0; i < n; ++i)
            cnt[i] = 1 << i;
    }

    int& operator[](int i) { return cnt[i]; }
    void flip(int i) {
        int val = tree[i += 1 << n] ? -1 : 1;
        for (int d = n; d--; i >>= 1) {
            if (tree[i] == 0 || tree[i] == 1 << (n - d)) --cnt[d];
            tree[i] += val;
            if (tree[i] == 0 || tree[i] == 1 << (n - d)) ++cnt[d];
        }
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef palilo
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    int n, q;
    cin >> n >> q;

    int64_t total = 0; // # of nodes
    for (int i = 0; i < n; ++i)
        total += 1ll * (1 << i) * (1 << i);

    segtree row(n), col(n);

    for (int i; q--;) {
        char c;
        cin >> c >> i, --i;
        (c == '0' ? row : col).flip(i);

        int64_t grey = total;
        for (int i = 0; i < n; ++i)
            grey -= row[i] * col[i];
        cout << grey * 4 + 1 << '\n';
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 70.0

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