Submission #1187417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187417		simona1230	Dancing Elephants (IOI11_elephants)	C++20	26 / 100	4906 ms	5264 KiB

elephants

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

const int s1=400;
const int s2=400;
const int s3=400;
const int maxn=150001;

int n,l;
int x[maxn];
multiset<int> s[s2];

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

void rebuild()
{
    vector<int> v;
    for(int i=0;i<n;i++)
        v.push_back(x[i]);

    sort(v.begin(),v.end());

    for(int i=0;i<n;i+=s1)
    {
        s[i/s1].clear();
        for(int j=0;j<s1;j++)
        {
            if(i+j>=n)break;
            //cout<<"|>"<<v[i+j]<<endl;
            s[i/s1].insert(v[i+j]);
        }
    }
}

map<int,int> cnt,id;

void build(int i)
{
    auto it=s[i].end();
    while(it!=s[i].begin())
    {
        it--;
        int h=*it+l;
        auto it1=s[i].upper_bound(h);
        if(it1==s[i].end())
        {
            cnt[*it]=1;
            id[*it]=*it;
        }
        else
        {
            cnt[*it]=cnt[*it1]+1;
            id[*it]=id[*it1];
        }
    }
}

int fb(int y)
{
    for(int i=0;i<s2-1;i++)
    {
        if(s[i].size()==0)continue;
        auto it=s[i].end();
        it--;
        if(y<=*it)return i;
    }
    return s2-1;
}


int num=0;
int update(int i, int y)
{
    num++;
    if(num%s3==1)
    {
        x[i]=y;
        rebuild();

        /*cout<<"*"<<endl;
        for(int i=0;i<s2;i++)
        {
            for(auto it=s[i].begin();it!=s[i].end();it++)
                cout<<*it<<" ";
            cout<<endl;
        }
        cout<<"="<<endl;*/

        for(int i=0;i<s2;i++)
            build(i);
    }
    else
    {
        int b1=fb(x[i]);
        s[b1].erase(x[i]);
        int b2=fb(y);
        s[b2].insert(y);
        x[i]=y;

        //cout<<"-- "<<b1<<" "<<b2<<endl;

        build(b1);
        build(b2);
    }

    int ans=0,c=-1;
    for(int i=0;i<s2;i++)
    {
        auto it=s[i].upper_bound(c);
        if(it==s[i].end())continue;

        //cout<<*it<<" "<<cnt[*it]<<" "<<id[*it]<<endl;

        ans+=cnt[*it];
        c=id[*it]+l;
    }

    //cout<<"!! "<<ans<<endl;

    return ans;
}

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