Submission #1135177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135177		gyg	Dancing Elephants (IOI11_elephants)	C++20	26 / 100	9088 ms	9292 KiB

elephants

// NOTE: 0-indexed
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array 
#define vec vector
#define pb push_back 
#define pii pair<int, int>
#define fir first 
#define sec second 
#define lb lower_bound
#define ub upper_bound
const int N = 2e5 + 5, PS = 1e9;

int n, l;
int sq1, sq2;
arr<int, N> ps;

map<int, int> at;
vec<pii> rng;
vec<set<int>> lst;
map<int, pii> jmp;
void cmp(int id) {
    for (auto it = jmp.lb(rng[id].fir); it != jmp.end() && it->fir <= rng[id].sec;) it = jmp.erase(it); 

    for (auto it = lst[id].rbegin(); it != lst[id].rend(); it++) {
        int x = *it;
        auto nx = lst[id].ub(x + l);
        if (nx == lst[id].end()) jmp[x] = {1, x + l};
        else jmp[x] = {jmp[*nx].fir + 1, jmp[*nx].sec};
    }
}
void bld() {
    rng.clear(), lst.clear(), jmp.clear();

    pii cr_rng = {0, 0}; set<int> cr_lst;
    for (pii x : at) {
        cr_rng.sec = x.fir, cr_lst.insert(x.fir);
        if (cr_lst.size() >= sq1) {
            rng.pb(cr_rng), lst.pb(cr_lst);
            cr_rng = {cr_rng.sec + 1, cr_rng.sec + 1}, cr_lst.clear();
        }
    }
    cr_rng.sec = PS;
    rng.pb(cr_rng), lst.pb(cr_lst);

    for (int i = 0; i < rng.size(); i++) cmp(i);

    // cout << "SQRT: " << sq << '\n';
    // for (pii x : rng)
    //     cout << x.fir << " " << x.sec << '\n';

    // for (pair<int, pii> x : jmp) {
    //     cout << x.fir << ": " << x.sec.fir << " " << x.sec.sec << '\n';
    // }
}

void init(int _n, int _l, int _ps[]) {
    n = _n, l = _l; assert(n <= 70000);

    if (n <= 50000) {
        sq1 = 150, sq2 = 500;
    } else {
        sq1 = 200, sq2 = 800;
    }
    
    for (int i = 1; i <= n; i++) ps[i] = _ps[i - 1];

    for (int i = 1; i <= n; i++) at[ps[i]]++;
    bld();
}

int rsp() {
    int ans = 0, prv = -1;
    for (int i = 0; i < rng.size(); i++) {
        auto it = lst[i].ub(prv);
        if (it == lst[i].end()) continue;
        ans += jmp[*it].fir, prv = jmp[*it].sec;
    }
    return ans;
}

int fnd(int x) {
    for (int i = 0; i < rng.size(); i++)
        if (rng[i].fir <= x && x <= rng[i].sec) return i;
    assert(false); return -1;
}

int cnt;
int update(int i, int nw_ps) {
    i++;

    int j = fnd(ps[i]), k = fnd(nw_ps);
    at[ps[i]]--; if (at[ps[i]] == 0) at.erase(ps[i]), lst[j].erase(ps[i]);
    at[nw_ps]++; lst[k].insert(nw_ps);
    ps[i] = nw_ps;
    cmp(j), cmp(k);

    int ans = rsp();
    cnt++;
    if (cnt >= sq2) 
        bld(), cnt = 0;
    return ans;
}

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