oj.uz

Submission #329156

# Submission time Handle Problem Language Result Execution time Memory
329156 2020-11-19T14:46:04 Z dolphingarlic Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 12908 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 3532 ms 2576 KB Output is correct
8 Correct 3722 ms 2836 KB Output is correct
9 Correct 3636 ms 4496 KB Output is correct
10 Correct 1656 ms 4332 KB Output is correct
11 Correct 1433 ms 4332 KB Output is correct
12 Correct 4221 ms 4716 KB Output is correct
13 Correct 1570 ms 4204 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 3532 ms 2576 KB Output is correct
8 Correct 3722 ms 2836 KB Output is correct
9 Correct 3636 ms 4496 KB Output is correct
10 Correct 1656 ms 4332 KB Output is correct
11 Correct 1433 ms 4332 KB Output is correct
12 Correct 4221 ms 4716 KB Output is correct
13 Correct 1570 ms 4204 KB Output is correct
14 Correct 3414 ms 3704 KB Output is correct
15 Correct 4796 ms 3564 KB Output is correct
16 Correct 5972 ms 4980 KB Output is correct
17 Correct 6266 ms 6088 KB Output is correct
18 Correct 6016 ms 5920 KB Output is correct
19 Correct 5249 ms 6112 KB Output is correct
20 Correct 6294 ms 5960 KB Output is correct
21 Correct 6076 ms 5956 KB Output is correct
22 Correct 2386 ms 5540 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 3532 ms 2576 KB Output is correct
8 Correct 3722 ms 2836 KB Output is correct
9 Correct 3636 ms 4496 KB Output is correct
10 Correct 1656 ms 4332 KB Output is correct
11 Correct 1433 ms 4332 KB Output is correct
12 Correct 4221 ms 4716 KB Output is correct
13 Correct 1570 ms 4204 KB Output is correct
14 Correct 3414 ms 3704 KB Output is correct
15 Correct 4796 ms 3564 KB Output is correct
16 Correct 5972 ms 4980 KB Output is correct
17 Correct 6266 ms 6088 KB Output is correct
18 Correct 6016 ms 5920 KB Output is correct
19 Correct 5249 ms 6112 KB Output is correct
20 Correct 6294 ms 5960 KB Output is correct
21 Correct 6076 ms 5956 KB Output is correct
22 Correct 2386 ms 5540 KB Output is correct
23 Execution timed out 9081 ms 12908 KB Time limit exceeded
24 Halted 0 ms 0 KB -