Submission #12893

#	Time	Username	Problem	Language	Result	Execution time	Memory
12893		tncks0121	즐거운 사진 수집 (JOI13_collecting)	C++14	30 / 100	28 ms	38540 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;
    node (int s = 0, ll c = 1): s(s), c(c) { }
};

node merge (node a, node b, int h) {
    node ret;
    ret.s = a.s + b.s;
    ret.c = 1 + ((ret.s == 0 || ret.s == (1<<h)) ? 0 : 2 * (a.c + b.c));
    return ret;
}

ll ans;

node tree[2][N_];
ll full[2][K_+3];
bool cur[2][N_+N_+2];

ll calc (node nd, ll *fl, int h) {
    if(nd.c == 1) return (full[0][h] + full[1][h] - fl[h]);
    return 1ll << h;
}

ll getans (node *tr, ll *fl, int x, int h) {
    if(tr[x].c == 1) return calc(tr[x], fl, h);
    return getans(tr, fl, x+x, h+1) + getans(tr, fl, x+x+1, h+1) + calc(tr[x], fl, h);
}

void upd (node *tr, ll *fl, int x, int v) {
    x += N;
    tr[x] = node(v, 1);
    
    //printf("%d %d %d %lld - %lld\n", x, K, tr[x].s, tr[x].c,calc(tr[x], fl, K));
    for(int h = K-1; x >>= 1; h--) {
        //ans -= calc(tr[x], fl, h);
        fl[h] -= tr[x].c;
        tr[x] = merge(tr[x+x], tr[x+x+1], K-h);
        //printf("%d %d %d %lld - %lld\n", x, h, tr[x].s, tr[x].c,calc(tr[x], fl, h));
        fl[h] += tr[x].c;
    }
    
    ans = getans (tr, fl, 1, 0);
}


int main() {
    
    scanf("%d%d", &K, &Q); N = 1<<K;
    
    ans = 1;
    for(int h = 0; h <= K; h++) full[0][h] = full[1][h] = 1 << h;
    
    while(Q--) {
        int t, x; scanf("%d%d", &t, &x); --x;
        cur[t][x] = !cur[t][x];
        //printf("{%d, %d}\n", t,x);
        upd(tree[t], full[t], x, cur[t][x]);
        printf("%lld\n", ans);
    }
    
    return 0;
}

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