Submission #1157057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157057		alexdd	Dancing Elephants (IOI11_elephants)	C++20	26 / 100	12 ms	3652 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int BUC = 400;
const int CNT_BUC = 400;
const int RECALC_TIME = 400;

int n,L;

int a[150005];

struct bucket
{
    multiset<int> s;
    vector<int> v;
    int cnt[BUC+RECALC_TIME+5],ri[BUC+RECALC_TIME+5];
    void calc_dp()
    {
        v.clear();
        for(auto it:s)
            v.push_back(it);
        assert((int)v.size() < BUC + RECALC_TIME + 5);
        int poz = (int)v.size();
        for(int i=(int)v.size()-1;i>=0;i--)
        {
            while(poz-1>=0 && v[poz-1] > v[i] + L)
                poz--;
            if(poz == (int)v.size())
            {
                cnt[i] = 1;
                ri[i] = v[i] + L;
            }
            else
            {
                cnt[i] = cnt[poz] + 1;
                ri[i] = ri[poz];
            }
        }
    }
    void init(vector<int> aux)
    {
        s.clear();
        v.clear();
        v = aux;
        for(int x:aux)
            s.insert(x);

        calc_dp();
    }
    void baga(int x)
    {
        s.insert(x);
        calc_dp();
    }
    void scoate(int x)
    {
        s.erase(s.find(x));
        calc_dp();
    }
    pair<int,int> get(int le)
    {
        int pozle = upper_bound(v.begin(),v.end(),le) - v.begin();
        if(pozle == (int)v.size())
            return {0,le};
        return {cnt[pozle], ri[pozle]};
    }
};

bucket buckets[CNT_BUC+5];
pair<int,int> ord[150005];
int unde[150005];
int caple[CNT_BUC+5],cntb;
void calc_all()
{
    for(int i=0;i<n;i++)
        ord[i] = {a[i], i};
    sort(ord,ord+n);

    cntb=0;
    for(int le=0;le<n;le+=BUC)
    {
        int ri = min(le+BUC-1, n-1);
        vector<int> aux;
        for(int i=le;i<=ri;i++)
        {
            aux.push_back(ord[i].first);
            unde[ord[i].second] = cntb;
        }

        caple[cntb] = le;
        buckets[cntb].init(aux);

        cntb++;
    }
}

void init(int N, int citL, int X[])
{
    n = N;
    L = citL;
    for(int i=0;i<n;i++)
        a[i] = X[i];

    calc_all();
}

int update_cnt;
int update(int i, int y)
{
    buckets[unde[i]].scoate(a[i]);

    a[i] = y;
    unde[i] = -1;
    for(int b=0;b<cntb;b++)
    {
        if(b==cntb-1 || caple[b+1] > a[i])
        {
            unde[i] = b;
            break;
        }
    }
    assert(unde[i]!=-1);
    buckets[unde[i]].baga(a[i]);

    update_cnt++;
    if(update_cnt % RECALC_TIME == 0)
    {
        calc_all();
    }

    assert(cntb>0);
    pair<int,int> aux = buckets[0].get(-INF);
    int cnt = aux.first, le = aux.second;
    //cerr<<cnt<<" "<<le<<" dupa 0\n";
    for(int i=1;i<cntb;i++)
    {
        aux = buckets[i].get(le);
        cnt += aux.first;
        le = aux.second;
        //cerr<<aux.first<<" "<<aux.second<<" aux "<<i<<"\n";
    }
    return cnt;
}

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