oj.uz

Submission #12905

# Submission time Handle Problem Language Result Execution time Memory
12905 2015-01-19T11:16:16 Z tncks0121 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 2916 ms 102028 KB 
#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_+5];

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 102028 KB Output is correct
2 Correct 8 ms 102028 KB Output is correct
3 Correct 12 ms 102028 KB Output is correct
4 Correct 8 ms 102028 KB Output is correct
5 Correct 8 ms 102028 KB Output is correct
6 Correct 12 ms 102028 KB Output is correct
7 Correct 0 ms 102028 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 102028 KB Output is correct
2 Correct 12 ms 102028 KB Output is correct
3 Correct 12 ms 102028 KB Output is correct
4 Correct 16 ms 102028 KB Output is correct
5 Correct 4 ms 102028 KB Output is correct
6 Correct 8 ms 102028 KB Output is correct
7 Correct 12 ms 102028 KB Output is correct
8 Correct 0 ms 102028 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2864 ms 102028 KB Output is correct
2 Correct 2896 ms 102028 KB Output is correct
3 Correct 2492 ms 102028 KB Output is correct
4 Correct 2916 ms 102028 KB Output is correct
5 Correct 2796 ms 102028 KB Output is correct
6 Correct 2764 ms 102028 KB Output is correct
7 Correct 2820 ms 102028 KB Output is correct
8 Correct 2792 ms 102028 KB Output is correct
9 Correct 2364 ms 102028 KB Output is correct
10 Correct 2592 ms 102028 KB Output is correct
11 Correct 2740 ms 102028 KB Output is correct
12 Correct 2776 ms 102028 KB Output is correct
13 Correct 2456 ms 102028 KB Output is correct