oj.uz

Submission #12903

# Submission time Handle Problem Language Result Execution time Memory
12903 2015-01-19T11:10:38 Z tncks0121 즐거운 사진 수집 (JOI13_collecting) C++14
30 / 100
 3112 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_];
bool cur[2][N_];

ll coef0[K_];

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

Subtask #3
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3112 ms 102028 KB Output isn't correct
2 Halted 0 ms 0 KB -