oj.uz

Submission #787402

# Submission time Handle Problem Language Result Execution time Memory
787402 2023-07-19T06:55:19 Z puppy 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 3708 ms 49752 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 212 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 4 ms 328 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 3 ms 304 KB Output is correct
8 Correct 3 ms 340 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3708 ms 45116 KB Output is correct
2 Correct 3660 ms 45244 KB Output is correct
3 Correct 3366 ms 33900 KB Output is correct
4 Correct 3641 ms 49752 KB Output is correct
5 Correct 3700 ms 49360 KB Output is correct
6 Correct 3706 ms 48140 KB Output is correct
7 Correct 3646 ms 49392 KB Output is correct
8 Correct 3637 ms 49412 KB Output is correct
9 Correct 3270 ms 35528 KB Output is correct
10 Correct 3486 ms 34564 KB Output is correct
11 Correct 3498 ms 43120 KB Output is correct
12 Correct 3492 ms 42792 KB Output is correct
13 Correct 3455 ms 34392 KB Output is correct