oj.uz

Submission #12904

# Submission time Handle Problem Language Result Execution time Memory
12904 2015-01-19T11:11:21 Z tncks0121 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 3076 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_];

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 4 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 4 ms 102028 KB Output is correct
5 Correct 12 ms 102028 KB Output is correct
6 Correct 8 ms 102028 KB Output is correct
7 Correct 12 ms 102028 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3076 ms 102028 KB Output is correct
2 Correct 2840 ms 102028 KB Output is correct
3 Correct 2552 ms 102028 KB Output is correct
4 Correct 2784 ms 102028 KB Output is correct
5 Correct 2896 ms 102028 KB Output is correct
6 Correct 2756 ms 102028 KB Output is correct
7 Correct 2840 ms 102028 KB Output is correct
8 Correct 2836 ms 102028 KB Output is correct
9 Correct 2396 ms 102028 KB Output is correct
10 Correct 2576 ms 102028 KB Output is correct
11 Correct 2684 ms 102028 KB Output is correct
12 Correct 2744 ms 102028 KB Output is correct
13 Correct 2596 ms 102028 KB Output is correct