제출 #198317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198317		nvmdava	즐거운 사진 수집 (JOI13_collecting)	C++17	100 / 100	4003 ms	242648 KiB

collecting

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70