제출 #1157086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157086		alexdd	Dancing Elephants (IOI11_elephants)	C++20	100 / 100	6388 ms	8896 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
{
    vector<int> v;
    int cnt[BUC+RECALC_TIME+5],ri[BUC+RECALC_TIME+5];
    void calc_dp()
    {
        assert((int)v.size() < BUC + RECALC_TIME + 5);
        sort(v.begin(),v.end());

        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)
    {
        v = aux;
        calc_dp();
    }
    void baga(int x)
    {
        v.push_back(x);
        calc_dp();
    }
    void scoate(int x)
    {
        bool gasit=0;
        for(int i=0;i<v.size();i++)
        {
            if(v[i]==x)
            {
                v.erase(v.begin()+i);
                gasit=1;
                break;
            }
        }
        assert(gasit);
        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] = ord[le].first;
        buckets[cntb].init(aux);

        cntb++;
    }
    assert(cntb < CNT_BUC);
}

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

int update_cnt;
int32_t update(int32_t i, int32_t 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;
            caple[b] = min(caple[b], a[i]);
            break;
        }
    }
    assert(unde[i]!=-1);
    buckets[unde[i]].baga(a[i]);

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

    assert(cntb>0);
    int cnt=0, poz=-INF;
    for(int i=0;i<cntb;i++)
    {
        pair<int,int> aux = buckets[i].get(poz);
        cnt += aux.first;
        poz = aux.second;
    }
    return cnt;
}

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