Submission #564352

#	Time	Username	Problem	Language	Result	Execution time	Memory
564352		hoanghq2004	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	4335 ms	26532 KiB

elephants

#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 (stderr)

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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3