Submission #423428

#	Time	Username	Problem	Language	Result	Execution time	Memory
423428		arayi	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9101 ms	4240 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
#include <set>
#define MP make_pair
#pragma GCC optimize("Os")
using namespace std;

const int N = 1e5 + 30;
int n, l;
set <pair<int, int> > fp;
int x[N], fr, sc;
int haj[N], nax[N], h[N];
void rmv(int i)
{
    bool bl = 0;
    if(i != fr && i != sc)
    {
        nax[haj[i]]= nax[i];
        haj[nax[i]] = haj[i];
        bl = 1;
    }
    fp.erase(MP(x[i], i));
    auto i1 = fp.end();
    fr = (*fp.begin()).second, sc = (*(--i1)).second;
    if(bl)
    {
        int v = i;
        while(v != fr)
        {
            v = nax[v];
            if(x[v] + l < x[nax[i]]) break;
            if(x[v] + l < x[haj[i]]) h[v] = haj[i];
        }
    }
}
void add(int i)
{
    auto i1 = fp.lower_bound(MP(x[i], i));
    if(i1 != fp.end()) nax[(*i1).second] = i, haj[i] = (*i1).second;
    if(i1 != fp.begin()) haj[(*(--i1)).second] = i, nax[i] = (*i1).second;
    fp.insert(MP(x[i], i));
    i1 = fp.end();
    fr = (*fp.begin()).second, sc = (*(--i1)).second;
    i1 = fp.lower_bound(MP(x[i] + l + 1, -1));
    if(i1 != fp.end()) h[i] = (*i1).second;
    int v = i;
    while(v != fr)
    {
        v = nax[v];
        if(x[v] + l < x[nax[i]]) break;
        if(x[v] + l < x[i]) h[v] = i;
    }
}
int go()
{
    int v = fr, sm = 1, nx = x[fr] + l;
    while(nx < x[sc])
    {
        sm++; v = h[v]; nx = x[v] + l;
    }
    return sm;
}
void init(int N, int L, int X[])
{
    n=N, l=L;
    for(int i = 0; i < n; i++)
    {
        x[i] = X[i];
        add(i);
    }
}

int update(int i, int y)
{
    rmv(i);
    x[i] = y;
    add(i);
    return go();
}

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