Submission #808574

#	Time	Username	Problem	Language	Result	Execution time	Memory
808574		Khizri	Dancing Elephants (IOI11_elephants)	C++17	10 / 100	6 ms	9684 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5,MAX=1e9+5;
int n,k,mx,ans,nxt=1,arr[mxn],L[mxn*20],R[mxn*20],loc[mxn],idx[mxn];
ll tree[mxn*20];
multiset<int>st[mxn];
set<int>total;
set<int>camera;
map<int,int>mp;
map<int,int>mp2;
void init(int N, int L, int X[])
{
    n=N,k=L;
    for(int i=1;i<=n;i++){
        arr[i]=X[i-1]+1;
        total.insert(arr[i]);
    }
    loc[1]=arr[1];
    st[1].insert(arr[1]);
    camera.insert(loc[1]);
    mp2[loc[1]]=1;
    idx[1]=1;
    mp[arr[1]]=1;
    mx=1;
    for(int i=2;i<=n;i++){
        if(arr[i]-loc[mx]>k){
            loc[++mx]=arr[i];
            idx[i]=mx;
            st[mx].insert(arr[i]);
            camera.insert(loc[mx]);
            mp2[loc[mx]]=mx;
            mp[arr[i]]=i;
        }
        else{
            idx[i]=mx;
            mp[arr[i]]=i;
            st[mx].insert(arr[i]);
        }
    }
    ans=mx;
}
void del(int pos,int val){
    st[pos].erase(val);
}
void add(int pos,int val){
    st[pos].insert(val);
    int id=mp[val];
    idx[id]=pos;
}
int update(int i, int y)
{
    i++,y++;
    st[idx[i]].erase(st[idx[i]].find(arr[i]));
    if(st[idx[i]].size()==0){
        ans--;
        camera.erase(loc[idx[i]]);
    }
    else if(*st[idx[i]].begin()!=loc[idx[i]]){
        camera.erase(loc[idx[i]]);
        loc[idx[i]]=*st[idx[i]].begin();
        camera.insert(loc[idx[i]]);
        mp2[loc[idx[i]]]=idx[i];
    }
    arr[i]=y;
    mp[y]=i;
    auto it=camera.upper_bound(arr[i]);
    if(it!=camera.begin()){
        it--;
        int x=*it;
        auto it2=camera.upper_bound(x-1);
        if(it2!=camera.begin()){
            it2--;
            int l=*it2,r=x;
            int lpos=mp2[l],rpos=mp2[r];
            while(st[rpos].size()&&*st[rpos].begin()-l<=k){
                int nw=*st[rpos].begin();
                del(rpos,nw);
                add(lpos,nw);
            }
            if(st[rpos].size()==0){
                camera.erase(r);
                ans--;
            }
            else{
                int first=*st[rpos].begin();
                if(first!=r){
                    camera.erase(r);
                    loc[mp2[r]]=first;
                    mp2[first]=mp2[r];
                    camera.insert(first);
                }
            }
        }
        it=camera.upper_bound(arr[i]);
        it--;
        x=*it;
        if(arr[i]-x<=k){
            add(mp2[x],arr[i]);
            return ans;
        }
    }
    it=camera.lower_bound(arr[i]);
    if(it!=camera.end()){
        int x=*it;
        int pos=mp2[x];
        int last=*(--st[pos].end());
        if(last-arr[i]<=k){
            loc[pos]=arr[i];
            mp2[arr[i]]=pos;
            camera.erase(x);
            camera.insert(arr[i]);
            add(pos,arr[i]);
            return ans;
        }
    }
    ans++;
    mx++;
    loc[mx]=arr[i];
    mp2[loc[mx]]=mx;
    camera.insert(arr[i]);
    add(mx,arr[i]);
    return ans;
}

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