Submission #329156

#	Time	Username	Problem	Language	Result	Execution time	Memory
329156		dolphingarlic	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	9081 ms	12908 KiB

elephants

#include "elephants.h"

#include <vector>
#include <algorithm>
#include <utility>
#include <climits>
#include <iostream>
#define ALL(x) x.begin(), x.end()
using namespace std;

const int MX_N = 150000, B = 750;

int n, l, x[MX_N];
vector<pair<int, int>> bckt[MX_N / B + 1];
int b_idx[MX_N];
pair<int, int> dp[MX_N];
int to_reset;
pair<int, int> by_x[MX_N];

void reset() {
    for (int i = 0; i < n; i++) by_x[i] = {x[i], i};
    sort(by_x, by_x + n);
    for (int i = 0; i <= MX_N / B; i++) bckt[i].clear();
    for (int i = 0; i < n; i++) {
        bckt[i / B].push_back(by_x[i]);
        b_idx[by_x[i].second] = i / B;
    }
    for (int i = 0; i <= MX_N / B; i++) {
        for (int j = bckt[i].size() - 1; ~j; j--) {
            int ub = upper_bound(ALL(bckt[i]), make_pair(bckt[i][j].first + l, INT_MAX)) - bckt[i].begin();
            if (ub == int(bckt[i].size())) dp[bckt[i][j].second] = {1, bckt[i][j].first + l};
            else {
                dp[bckt[i][j].second] = dp[bckt[i][ub].second];
                dp[bckt[i][j].second].first++;
            }
        }
    }
    to_reset = B;
}

void init(int N, int L, int X[]) {
    n = N, l = L;
    for (int i = 0; i < n; i++) x[i] = X[i];
    reset();
}

int update(int i, int y) {
    // Erase elephant i and update bucket
    bckt[b_idx[i]].erase(find(ALL(bckt[b_idx[i]]), make_pair(x[i], i)));
    for (int j = bckt[b_idx[i]].size() - 1; ~j; j--) {
        int ub = upper_bound(ALL(bckt[b_idx[i]]), make_pair(bckt[b_idx[i]][j].first + l, INT_MAX)) - bckt[b_idx[i]].begin();
        if (ub == int(bckt[b_idx[i]].size())) dp[bckt[b_idx[i]][j].second] = {1, bckt[b_idx[i]][j].first + l};
        else {
            dp[bckt[b_idx[i]][j].second] = dp[bckt[b_idx[i]][ub].second];
            dp[bckt[b_idx[i]][j].second].first++;
        }
    }
    // Insert elephant i and update bucket
    x[i] = y;
    for (int new_b = 0; new_b <= MX_N / B; new_b++) {
        if ((bckt[new_b].size() && bckt[new_b].back().first >= x[i]) || new_b == MX_N / B) {
            bckt[new_b].insert(upper_bound(ALL(bckt[new_b]), make_pair(x[i], i)), make_pair(x[i], i));
            for (int j = bckt[new_b].size() - 1; ~j; j--) {
                int ub = upper_bound(ALL(bckt[new_b]), make_pair(bckt[new_b][j].first + l, INT_MAX)) - bckt[new_b].begin();
                if (ub == int(bckt[new_b].size())) dp[bckt[new_b][j].second] = {1, bckt[new_b][j].first + l};
                else {
                    dp[bckt[new_b][j].second] = dp[bckt[new_b][ub].second];
                    dp[bckt[new_b][j].second].first++;
                }
            }
            b_idx[i] = new_b;
            break;
        }
    }
    // Reset buckets after B queries
    if (!--to_reset) reset();
    // Get the answer
    int ans = 0;
    for (int j = 0, curr_x = -1; j <= MX_N / B; j++) if (bckt[j].size() && curr_x < bckt[j].back().first) {
        int ub = upper_bound(ALL(bckt[j]), make_pair(curr_x, INT_MAX))->second;
        ans += dp[ub].first;
        curr_x = dp[ub].second;
    }
    return ans;
}

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