oj.uz

Submission #382539

# Submission time Handle Problem Language Result Execution time Memory
382539 2021-03-27T15:45:11 Z phathnv 즐거운 사진 수집 (JOI13_collecting) C++11
100 / 100
 2154 ms 78356 KB 
#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.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2154 ms 78100 KB Output is correct
2 Correct 2115 ms 78116 KB Output is correct
3 Correct 1776 ms 58808 KB Output is correct
4 Correct 2041 ms 78356 KB Output is correct
5 Correct 1933 ms 77904 KB Output is correct
6 Correct 2001 ms 76908 KB Output is correct
7 Correct 1991 ms 78196 KB Output is correct
8 Correct 2013 ms 78232 KB Output is correct
9 Correct 1749 ms 57544 KB Output is correct
10 Correct 1804 ms 59812 KB Output is correct
11 Correct 1880 ms 76900 KB Output is correct
12 Correct 1927 ms 76660 KB Output is correct
13 Correct 1760 ms 59956 KB Output is correct