Submission #269610

#	Time	Username	Problem	Language	Result	Execution time	Memory
269610		PeppaPig	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	Compilation error	0 ms	0 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1.5e5 + 5;
const int B = 390;

int n, k;
int start[B], pos[N], id[N], jump[N], cnt[N];
vector<pii> bucket[B + 1];
set<pii> S;

void solve_bucket(int idx) {
    // printf("bucket %d\n ---- ", idx);

    vector<pii> &vec = bucket[idx];
    for(int i = vec.size() - 1; ~i; i--) {
        int now, x; tie(x, now) = vec[i];

        // printf("(%d %d), ", x, now);

        auto it = S.lower_bound(pii(x + k + 1, -1e9));
        if(it == S.end()) jump[now] = -1, cnt[now] = 1;
        else {
            if(id[it->y] != idx) jump[now] = it->y, cnt[now] = 1;
            else jump[now] = jump[it->y], cnt[now] = cnt[it->y] + 1;
        }
    }
    // printf("\n");

    // printf("Set --- ");
    // for(pii p : S) printf("(%d %d), ", p.x, p.y);
    // printf("\n");
}

void init(int _n, int _k, int X[]) {
    n = _n, k = _k;
    fill_n(start, B, 1e9);

    for(int i = 0; i < n; i++) {
        pos[i] = X[i], id[i] = i / B;
        bucket[i / B].emplace_back(pos[i], i);
        S.emplace(pos[i], i);
    }
    for(int i = 0; i < B; i++) if(!bucket[i].empty()) {
        start[i] = bucket[i][0].x;
        solve_bucket(i);
    }
}

int add(int i, bool b) {
    int ptr = 0;
    while(ptr + 1 < B && start[ptr + 1] <= pos[i])
        ++ptr;

    int idx = lower_bound(bucket[ptr].begin(), bucket[ptr].end(), pii(pos[i], i)) - bucket[ptr].begin();
    if(b) {
        bucket[ptr].insert(bucket[ptr].begin() + idx, pii(pos[i], i));
        S.emplace(pos[i], i), id[i] = ptr;
    } else {
        bucket[ptr].erase(bucket[ptr].begin() + idx);
        S.erase(pii(pos[i], i));
    }

    return ptr;
}

void revalidate() {
    fill_n(start, B, 1e9);

    int ptr = 0;
    for(pii p : S) {
        if(!ptr || (ptr - 1) / B != ptr / B)
            bucket[ptr / B].clear();
        bucket[ptr / B].emplace_back(p);
        id[p.y] = ptr / B;
        ++ptr;
    }
    for(int i = 0; i < B; i++) if(!bucket[i].empty()) {
        start[i] = bucket[i][0].x;
        solve_bucket(i);
    }
}

int counter;

int update(int i, int y) 
    int ba = add(i, 0);
    pos[i] = y;
    int bb = add(i, 1);
    solve_bucket(ba), solve_bucket(bb);

    // for(int i = 0; i < n; i++) printf("(%d %d)\n", jump[i], cnt[i]);

    int now = S.begin()->y, answer = 0;
    while(now != -1) {
        answer += cnt[now];
        now = jump[now];
    }

    // printf("answer = %d\n", answer);

    return answer;
}

Compilation message (stderr)

elephants.cpp:93:5: error: expected initializer before 'int'
   93 |     int ba = add(i, 0);
      |     ^~~
elephants.cpp:94:5: error: 'pos' does not name a type
   94 |     pos[i] = y;
      |     ^~~
elephants.cpp:95:18: error: 'i' was not declared in this scope
   95 |     int bb = add(i, 1);
      |                  ^
elephants.cpp:96:17: error: expected constructor, destructor, or type conversion before '(' token
   96 |     solve_bucket(ba), solve_bucket(bb);
      |                 ^
elephants.cpp:101:5: error: expected unqualified-id before 'while'
  101 |     while(now != -1) {
      |     ^~~~~
elephants.cpp:108:5: error: expected unqualified-id before 'return'
  108 |     return answer;
      |     ^~~~~~
elephants.cpp:109:1: error: expected declaration before '}' token
  109 | }
      | ^