oj.uz

Submission #564352

# Submission time Handle Problem Language Result Execution time Memory
564352 2022-05-19T03:26:37 Z hoanghq2004 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 4335 ms 26532 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "elephants.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 15e4;
const int S = 600;

int n, L;
vector <int> s[2 * N / S + 10];
map <int, int> mp;
int f[N / S + 10][5 * S];
int g[N / S + 10][5 * S];

void calc(int id) {
    for (int i = s[id].size() - 1, j = s[id].size() - 1; i >= 0; --i) {
        while (j >= i && s[id][j] - s[id][i] > L) --j;
        if (j + 1 == s[id].size()) f[id][i] = 1, g[id][i] = s[id][i] + L + 1;
        else f[id][i] = f[id][j + 1] + 1, g[id][i] = g[id][j + 1];
    }
}

void add(int id, int x) {
    int j = lower_bound(s[id].begin(), s[id].end(), x) - s[id].begin();
    s[id].push_back(0);
    for (int i = s[id].size() - 1; i > j; --i) s[id][i] = s[id][i - 1];
    s[id][j] = x;
    calc(id);
}

void rev(int id, int x) {
    int j = lower_bound(s[id].begin(), s[id].end(), x) - s[id].begin();
    for (int i = j; i + 1 < s[id].size(); ++i) s[id][i] = s[id][i + 1];
    s[id].pop_back();
    calc(id);
}

int cnt;

int FindId(int x) {
    if (x < s[0].front()) return 0;
    int L = 0, R = cnt;
    while (L < R) {
        int mid = L + R >> 1;
        if (s[mid].size() && x > s[mid].back()) L = mid + 1;
        else R = mid;
    }
    return L;
}

void rebuild() {
    for (int i = 0; i <= cnt; ++i) s[i].clear();
    cnt = 0;
    for (auto [x, o]: mp) {
        if (!o) continue;
        if (s[cnt].size() == S) ++cnt;
        s[cnt].push_back(x);
    }
    for (int i = 0; i <= cnt; ++i) calc(i);
}

int jump() {
    int last = -1;
    for (int i = cnt; i >= 0; --i)
        if (s[i].size()) {
            last = s[i].back();
            break;
        }
    int cur = s[0].front();
    int id = 0;
    int need = 0;
    while (cur <= last) {
        if (s[id].size() && cur <= s[id].back()) {
            int i = lower_bound(s[id].begin(), s[id].end(), cur) - s[id].begin();
            need += f[id][i];
            cur = g[id][i];
        }
        ++id;
    }
    return need;
}

int a[N];

void init(int _n, int _L, int x[]) {
    L = _L;
    for (int i = 0; i < _n; ++i) a[i] = x[i], ++mp[a[i]];
    n = _n;
    rebuild();
}

int cnt_queries;

int update(int i, int x) {
    ++cnt_queries;
    if (cnt_queries == S) {
        cnt_queries = 0;
        rebuild();
    }
    if (!--mp[a[i]]) {
        int id = FindId(a[i]);
        rev(id, a[i]);
    }
    a[i] = x;
    if (!mp[a[i]]++) {
        int id = FindId(a[i]);
        add(id, a[i]);
    }
    return jump();
}

Compilation message

elephants.cpp: In function 'void calc(int)':
elephants.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if (j + 1 == s[id].size()) f[id][i] = 1, g[id][i] = s[id][i] + L + 1;
      |             ~~~~~~^~~~~~~~~~~~~~~
elephants.cpp: In function 'void rev(int, int)':
elephants.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = j; i + 1 < s[id].size(); ++i) s[id][i] = s[id][i + 1];
      |                     ~~~~~~^~~~~~~~~~~~~~
elephants.cpp: In function 'int FindId(int)':
elephants.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int mid = L + R >> 1;
      |                   ~~^~~
elephants.cpp: In function 'void rebuild()':
elephants.cpp:62:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for (auto [x, o]: mp) {
      |               ^

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 361 ms 5000 KB Output is correct
8 Correct 375 ms 5808 KB Output is correct
9 Correct 399 ms 7664 KB Output is correct
10 Correct 317 ms 8752 KB Output is correct
11 Correct 314 ms 8672 KB Output is correct
12 Correct 667 ms 8760 KB Output is correct
13 Correct 348 ms 8632 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 361 ms 5000 KB Output is correct
8 Correct 375 ms 5808 KB Output is correct
9 Correct 399 ms 7664 KB Output is correct
10 Correct 317 ms 8752 KB Output is correct
11 Correct 314 ms 8672 KB Output is correct
12 Correct 667 ms 8760 KB Output is correct
13 Correct 348 ms 8632 KB Output is correct
14 Correct 229 ms 5820 KB Output is correct
15 Correct 561 ms 7556 KB Output is correct
16 Correct 1086 ms 9800 KB Output is correct
17 Correct 1071 ms 11864 KB Output is correct
18 Correct 1247 ms 12072 KB Output is correct
19 Correct 643 ms 12496 KB Output is correct
20 Correct 1222 ms 12248 KB Output is correct
21 Correct 1142 ms 12220 KB Output is correct
22 Correct 624 ms 11768 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 361 ms 5000 KB Output is correct
8 Correct 375 ms 5808 KB Output is correct
9 Correct 399 ms 7664 KB Output is correct
10 Correct 317 ms 8752 KB Output is correct
11 Correct 314 ms 8672 KB Output is correct
12 Correct 667 ms 8760 KB Output is correct
13 Correct 348 ms 8632 KB Output is correct
14 Correct 229 ms 5820 KB Output is correct
15 Correct 561 ms 7556 KB Output is correct
16 Correct 1086 ms 9800 KB Output is correct
17 Correct 1071 ms 11864 KB Output is correct
18 Correct 1247 ms 12072 KB Output is correct
19 Correct 643 ms 12496 KB Output is correct
20 Correct 1222 ms 12248 KB Output is correct
21 Correct 1142 ms 12220 KB Output is correct
22 Correct 624 ms 11768 KB Output is correct
23 Correct 3105 ms 23908 KB Output is correct
24 Correct 3019 ms 23264 KB Output is correct
25 Correct 2158 ms 22372 KB Output is correct
26 Correct 2445 ms 26532 KB Output is correct
27 Correct 2499 ms 26412 KB Output is correct
28 Correct 1987 ms 9952 KB Output is correct
29 Correct 1930 ms 9400 KB Output is correct
30 Correct 2137 ms 9888 KB Output is correct
31 Correct 1875 ms 9332 KB Output is correct
32 Correct 2244 ms 26136 KB Output is correct
33 Correct 1209 ms 20396 KB Output is correct
34 Correct 2210 ms 26192 KB Output is correct
35 Correct 1067 ms 19508 KB Output is correct
36 Correct 64 ms 7708 KB Output is correct
37 Correct 1342 ms 19348 KB Output is correct
38 Correct 2625 ms 25180 KB Output is correct
39 Correct 2244 ms 26176 KB Output is correct
40 Correct 2952 ms 25180 KB Output is correct
41 Correct 4244 ms 25188 KB Output is correct
42 Correct 4335 ms 25616 KB Output is correct