Submission #787402

#	Time	Username	Problem	Language	Result	Execution time	Memory
787402		puppy	즐거운 사진 수집 (JOI13_collecting)	C++17	100 / 100	3708 ms	49752 KiB

collecting

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
struct SegTree
{
    vector<int> tree;
    vector<int> cnt;
    SegTree(int N)
    {
        int n = (int)ceil(log2(N));
        cnt.resize(n+1);
        int sz = 1 << ((int)ceil(log2(N))+1);
        tree.resize(sz);
    }
    void init(int s, int e, int node, int dep)
    {
        cnt[dep]++;
        if (s == e) return;
        init(s, (s+e)/2, 2*node, dep+1);
        init((s+e)/2+1, e, 2*node+1, dep+1);
    }
    void upd(int s, int e, int node, int id, int dep)
    {
        if (s == e) {
            tree[node] = !tree[node];
            return;
        }
        int m = s + e >> 1;
        if (id <= m) upd(s, m, 2*node, id, dep+1);
        else upd(m+1, e, 2*node+1, id, dep+1);
        if (tree[node] == 0 || tree[node] == e-s+1) cnt[dep]--;
        tree[node] = tree[2*node] + tree[2*node+1];
        if (tree[node] == 0 || tree[node] == e-s+1) cnt[dep]++;
    }
};
int main()
{
    int N, Q; cin >> N >> Q;
    vector<SegTree> seg(2, 1<<N);
    int sz = 1 << N;
    seg[0].init(0, sz-1, 1, 0);
    seg[1].init(0, sz-1, 1, 0);
    long long tot = 0;
    for (int i = 0; i <= N; i++) tot += 1LL << (2 * i);
    for (int i = 0; i < Q; i++) {
        int t, x; cin >> t >> x;
        if (t == 0) seg[0].upd(0, sz-1, 1, x-1, 0);
        else seg[1].upd(0, sz-1, 1, x-1, 0);
        long long tmp = 0;
        for (int i = 0; i <= N; i++) {
            tmp += (long long)seg[0].cnt[i] * seg[1].cnt[i];
        }
        cout << (tot - tmp) * 4 + 1 << '\n';
    }
}

Compilation message (stderr)

collecting.cpp: In member function 'void SegTree::upd(int, int, int, int, int)':
collecting.cpp:29:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int m = s + e >> 1;
      |                 ~~^~~

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