oj.uz

Submission #787403

# Submission time Handle Problem Language Result Execution time Memory
787403 2023-07-19T06:55:42 Z puppy 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 1062 ms 48652 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 344 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 360 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 956 ms 44072 KB Output is correct
2 Correct 1039 ms 44076 KB Output is correct
3 Correct 855 ms 33804 KB Output is correct
4 Correct 980 ms 44476 KB Output is correct
5 Correct 1031 ms 43872 KB Output is correct
6 Correct 943 ms 42792 KB Output is correct
7 Correct 1014 ms 44140 KB Output is correct
8 Correct 1062 ms 44116 KB Output is correct
9 Correct 842 ms 33008 KB Output is correct
10 Correct 948 ms 39860 KB Output is correct
11 Correct 1037 ms 48652 KB Output is correct
12 Correct 973 ms 46692 KB Output is correct
13 Correct 903 ms 42176 KB Output is correct