oj.uz

Submission #329175

# Submission time Handle Problem Language Result Execution time Memory
329175 2020-11-19T15:26:41 Z dolphingarlic Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 8300 KB 
#include "elephants.h"

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ALL(x) x.begin(), x.end()
using namespace std;

const int MX_N = 150000, B = 300, IB = 500;

int n, l, x[MX_N];
vector<pair<int, int>> bckt[IB];
int b_idx[MX_N];
pair<int, int> dp[MX_N];
int to_reset;
pair<int, int> by_x[MX_N];

inline 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 < IB; 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 < IB; 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 < IB; new_b++) {
        if ((bckt[new_b].size() && bckt[new_b].back().first >= x[i]) || new_b == IB - 1) {
            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 < IB; 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1231 ms 1792 KB Output is correct
8 Correct 1337 ms 1900 KB Output is correct
9 Correct 1346 ms 3052 KB Output is correct
10 Correct 1069 ms 3052 KB Output is correct
11 Correct 995 ms 3180 KB Output is correct
12 Correct 2248 ms 3076 KB Output is correct
13 Correct 1029 ms 3052 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1231 ms 1792 KB Output is correct
8 Correct 1337 ms 1900 KB Output is correct
9 Correct 1346 ms 3052 KB Output is correct
10 Correct 1069 ms 3052 KB Output is correct
11 Correct 995 ms 3180 KB Output is correct
12 Correct 2248 ms 3076 KB Output is correct
13 Correct 1029 ms 3052 KB Output is correct
14 Correct 1221 ms 2236 KB Output is correct
15 Correct 1677 ms 2284 KB Output is correct
16 Correct 3379 ms 3300 KB Output is correct
17 Correct 3979 ms 4332 KB Output is correct
18 Correct 3976 ms 4120 KB Output is correct
19 Correct 2710 ms 4204 KB Output is correct
20 Correct 3912 ms 4220 KB Output is correct
21 Correct 3849 ms 4120 KB Output is correct
22 Correct 1855 ms 4204 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1231 ms 1792 KB Output is correct
8 Correct 1337 ms 1900 KB Output is correct
9 Correct 1346 ms 3052 KB Output is correct
10 Correct 1069 ms 3052 KB Output is correct
11 Correct 995 ms 3180 KB Output is correct
12 Correct 2248 ms 3076 KB Output is correct
13 Correct 1029 ms 3052 KB Output is correct
14 Correct 1221 ms 2236 KB Output is correct
15 Correct 1677 ms 2284 KB Output is correct
16 Correct 3379 ms 3300 KB Output is correct
17 Correct 3979 ms 4332 KB Output is correct
18 Correct 3976 ms 4120 KB Output is correct
19 Correct 2710 ms 4204 KB Output is correct
20 Correct 3912 ms 4220 KB Output is correct
21 Correct 3849 ms 4120 KB Output is correct
22 Correct 1855 ms 4204 KB Output is correct
23 Execution timed out 9065 ms 8300 KB Time limit exceeded
24 Halted 0 ms 0 KB -