oj.uz

Submission #787407

# Submission time Handle Problem Language Result Execution time Memory
787407 2023-07-19T06:59:13 Z 이성호(#10033) 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 1117 ms 44376 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()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    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 0 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 232 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 44064 KB Output is correct
2 Correct 1117 ms 44044 KB Output is correct
3 Correct 904 ms 33880 KB Output is correct
4 Correct 1036 ms 44376 KB Output is correct
5 Correct 1113 ms 43808 KB Output is correct
6 Correct 1006 ms 42792 KB Output is correct
7 Correct 1071 ms 44060 KB Output is correct
8 Correct 1085 ms 44076 KB Output is correct
9 Correct 969 ms 32968 KB Output is correct
10 Correct 1006 ms 34768 KB Output is correct
11 Correct 1084 ms 43452 KB Output is correct
12 Correct 1027 ms 43264 KB Output is correct
13 Correct 879 ms 35012 KB Output is correct