oj.uz

Submission #198317

# Submission time Handle Problem Language Result Execution time Memory
198317 2020-01-25T15:16:19 Z nvmdava 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 4003 ms 242648 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 2500000
#define MOD 1000000007
 
int cnt[2][N];
 
struct Node{
    int L, R;
    int c = 1;
    Node *l = NULL, *r = NULL;
    Node(int _c, int _L, int _R){
        L = _L; R = _R; c = _c;
        l = NULL;
        r = NULL;
    }
    void update(int ty, int x){
        if(L == R){
            c ^= 3;
            return;
        }
        int M = (L + R) >> 1;
        if(!l){
            l = new Node(c, L, M);
            r = new Node(c, M + 1, R);
            cnt[ty][R - M] += 2;
        }
        
        if(x <= M)
            l -> update(ty, x);
        else
            r -> update(ty, x);
 
        if(l -> c == r -> c && l -> c){
            c = l -> c;
            cnt[ty][R - M] -= 2;
            delete(l); delete(r);
            l = NULL; r = NULL;
        } else {
            c = 0;
        }
    }
} *t[2] = {NULL, NULL};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n, q;
    cin>>n>>q;
 
    int lim = 1 << n;
 
    t[0] = new Node(1, 1, lim);
    t[1] = new Node(1, 1, lim);
    cnt[0][lim] = cnt[1][lim] = 1;
    while(q--){
        int ty, x;
        cin>>ty>>x;
        t[ty] -> update(ty, x);
        ll res = 0;
        for(int i = 0; i <= n; ++i){
            res += (1LL << (n - i)) * (cnt[1][1 << i] + cnt[0][1 << i]) - 1LL * cnt[1][1 << i] * cnt[0][1 << i];
        }
        cout<<res<<'\n';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 376 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4003 ms 184048 KB Output is correct
2 Correct 3807 ms 184856 KB Output is correct
3 Correct 3320 ms 141232 KB Output is correct
4 Correct 3854 ms 242648 KB Output is correct
5 Correct 3972 ms 186860 KB Output is correct
6 Correct 3570 ms 82924 KB Output is correct
7 Correct 3740 ms 184576 KB Output is correct
8 Correct 3867 ms 184844 KB Output is correct
9 Correct 3166 ms 111820 KB Output is correct
10 Correct 3382 ms 142200 KB Output is correct
11 Correct 3749 ms 184176 KB Output is correct
12 Correct 3494 ms 82724 KB Output is correct
13 Correct 3221 ms 75656 KB Output is correct