oj.uz

Submission #198307

# Submission time Handle Problem Language Result Execution time Memory
198307 2020-01-25T14:35:54 Z nvmdava 즐거운 사진 수집 (JOI13_collecting) C++17
0 / 100
 243 ms 262148 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 1050000
#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;
    }
    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;
        } 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 243 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 192 ms 71828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -