Submission #12904

#	Time	Username	Problem	Language	Result	Execution time	Memory
12904		tncks0121	즐거운 사진 수집 (JOI13_collecting)	C++14	100 / 100	3076 ms	102028 KiB

collecting

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <iostream>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int K_ = 20;
const int N_ = 1<<20;

int N, Q, K;

struct node {
    int s; ll c, a;
    node (int s = 0, ll c = 1, ll a = 0): s(s), c(c), a(a) { }
};


node tree0[N_+N_+5], tree1[N_+N_+5];
ll full1[K_+5];
bool cur[2][N_];

ll coef0[K_+5];

node merge0 (node x, node y, int h) {
    node ret;
    ret.s = x.s + y.s;
    ret.c = (ret.s == 0 || ret.s == (1<<(K-h))) ? 1 : (1 + (x.c + y.c) * 2);
    ret.a = (ret.c == 1) ? 0 : ((1 << h) + (x.a + y.a));
    return ret;
}

void upd0 (int nd, int h, int x, int v) {
    if(nd >= N) {
        tree0[nd] = node(v, 1, 0);
        return;
    }
    
    int d = ((x >> (K - h - 1)) & 1);
    
    if(tree0[nd].c == 1) {
        coef0[h]--;
        coef0[h+1] += 2;
    }
    
    upd0(nd+nd+d, h + 1, x, v);
    
    tree0[nd] = merge0(tree0[nd+nd], tree0[nd+nd+1], h);
    
    if(tree0[nd].c == 1) {
        if(tree0[nd+nd].c == 1) coef0[h+1]--;
        if(tree0[nd+nd+1].c == 1) coef0[h+1]--;
        coef0[h]++;
    }
}

void upd1 (int x, int v) {
    x += N;
    tree1[x] = node(v, 1, 0);
    for(int h = K-1, u = x; u >>= 1; h--) {
        full1[h] -= tree1[u].c;
        tree1[u] = merge0(tree1[u+u], tree1[u+u+1], h);
        full1[h] += tree1[u].c;
    }
}

int main() {
    scanf("%d%d", &K, &Q); N = 1<<K;
    
    for(int h = 0; h <= K; h++) full1[h] = 1 << h;
    for(int h = 0, i = 1; i < N+N; i++) {
        tree0[i] = tree1[i] = node(0, 1, 0);
        if(i == (2<<h) - 1) ++h;
    }
    coef0[0] = 1;
    
    while(Q--) {
        int t, x; scanf("%d%d", &t, &x); --x;
        cur[t][x] = !cur[t][x];
        
        if(t == 0) {
            upd0(1, 0, x, cur[t][x]);
        }else {
            upd1(x, cur[t][x]);
        }
        
        ll ans = tree0[1].a;
        for(int i = 0; i <= K; i++) ans += coef0[i] * full1[i];
        
        printf("%lld\n", ans);
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70