Submission #382539

#	Time	Username	Problem	Language	Result	Execution time	Memory
382539		phathnv	즐거운 사진 수집 (JOI13_collecting)	C++11	100 / 100	2154 ms	78356 KiB

collecting

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct SegmentTree{
    int n, depth;
    vector<int> d, cnt;
    void init(int _depth){
        depth = _depth;
        n = (1 << depth);
        cnt.assign(depth, 0);
        d.assign(n * 4, 0);
        cnt[0] = 1;
        for(int i = 1; i < depth; i++)
            cnt[i] = cnt[i - 1] * 2;
    }
    void update(int id, int depth, int l, int r, int pos){
        if (pos < l || r < pos)
            return;
        if (l == r){
            d[id] ^= 1;
            return;
        }
        cnt[depth] -= (d[id] == 0 || d[id] == r - l + 1);
        int mid = (l + r) >> 1;
        update(id << 1, depth + 1, l, mid, pos);
        update(id << 1 | 1, depth + 1, mid + 1, r, pos);
        d[id] = d[id << 1] + d[id << 1 | 1];
        cnt[depth] += (d[id] == 0 || d[id] == r - l + 1);
    }

    void update(int pos){
        update(1, 0, 1, n, pos);
    }
} ST[2];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    for(int i = 0; i < 2; i++)
        ST[i].init(n);

    while (q--){
        int id, pos;
        cin >> id >> pos;
        ST[id].update(pos);

        ll res = 1;
        for(int i = 1; i <= n; i++)
            res = res * 4 + 1;
        for(int i = 0; i < n; i++)
            res -= (ll) ST[0].cnt[i] * ST[1].cnt[i] * 4;
        cout << res << '\n';
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70