Submission #97227

#	Time	Username	Problem	Language	Result	Execution time	Memory
97227		Alexa2001	Dancing Elephants (IOI11_elephants)	C++17	50 / 100	9053 ms	9336 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 7e4 + 5, lg = 17, inf = 2e9;
const int BS = 100;

typedef pair<int,int> Pair;

int n, L, nr_upd, where[Nmax];
set<Pair> S;
set<int> bad;

int go[lg+2][Nmax];
int prevpos;

bool active[Nmax];


void init(int N, int _L, int X[])
{
    nr_upd = 0;
    int i; L = _L; n = N;
    for(i=0; i<n; ++i)
    {
        where[i] = X[i];
        S.insert({X[i], i});
    }
}

void refresh_all()
{
    int i, j;
    set<Pair> :: iterator itt;

    for(auto it : S)
    {
        itt = S.upper_bound({ it.first + L, inf });
        go[0][it.second] = (itt == S.end() ? -1 : itt -> second);
    }
    for(i=1; i<=lg; ++i)
        for(j=0; j<n; ++j)
            if(go[i-1][j] == -1) go[i][j] = -1;
                else go[i][j] = go[i-1][go[i-1][j]];

    for(i=0; i<n; ++i) active[i] = 1;
    bad.clear();
}

int solve(int pos)
{
    assert(pos != prevpos);
    prevpos = pos;

    int i, ans = 0, lim;

    ///
    set<int> :: iterator it;
    set<Pair> :: iterator sk;
    ///

    it = bad.lower_bound(where[pos]);
    if(it == bad.end()) lim = inf;
        else lim = *it;

    while(where[pos] == lim || (go[0][pos] != -1 && active[go[0][pos]] && where[go[0][pos]] >= lim) || (go[0][pos] != -1 && !active[go[0][pos]])|| (go[0][pos] == -1 && lim < inf))
    {
        sk = S.upper_bound({ where[pos] + L, inf });
        if(sk == S.end()) return ans;

        ++ans;

        pos = sk->second;

        it = bad.lower_bound(where[pos]);
        if(it == bad.end()) lim = inf;
            else lim = *it;
    }

    for(i=lg; i>=0; --i)
        if(go[i][pos] != -1 && where[go[i][pos]] < lim && active[go[i][pos]])
            pos = go[i][pos], ans += (1<<i);

    if(go[0][pos] == -1 && lim == inf) return ans;
    return ans + solve(pos);
}

int solve2()
{
    set<Pair> :: iterator it;
    it = S.begin();

    int ans = 0;

    while(it != S.end())
    {
        it = S.upper_bound({ it->first + L, inf });
        ++ans;
    }
    return ans;
}

int update(int id, int y)
{
    if(nr_upd % BS == 0) refresh_all();
    ++nr_upd;

    bad.insert(where[id]);
    bad.insert(y);

 //   for(auto it : bad) cerr << it << ' '; cerr << '\n';

    S.erase(S.find({ where[id], id }));
    S.insert({ y, id }); where[id] = y;

    active[id] = 0;
    prevpos = -1;

    int curr = solve(S.begin() -> second) + 1;

 //   cerr << curr << ' ' << solve2() << '\n';
    return curr;
}

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