oj.uz

Submission #12893

# Submission time Handle Problem Language Result Execution time Memory
12893 2015-01-19T03:27:31 Z tncks0121 즐거운 사진 수집 (JOI13_collecting) C++14
30 / 100
 28 ms 38540 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;
    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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 38540 KB Output is correct
2 Correct 8 ms 38540 KB Output is correct
3 Correct 24 ms 38540 KB Output is correct
4 Correct 28 ms 38540 KB Output is correct
5 Correct 12 ms 38540 KB Output is correct
6 Correct 12 ms 38540 KB Output is correct
7 Correct 8 ms 38540 KB Output is correct
8 Correct 8 ms 38540 KB Output is correct

Subtask #3
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 38536 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -