Submission #269511

#	Time	Username	Problem	Language	Result	Execution time	Memory
269511		PeppaPig	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	170 ms	2816 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) {
    if(++counter % B == 0)
        revalidate();
    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;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3