Submission #731064

#	Time	Username	Problem	Language	Result	Execution time	Memory
731064		ogibogi2004	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	6922 ms	17008 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=7e4+6;
const int K=272;
int dp1[MAXN];
int dp2[MAXN];
int where[MAXN];
int where1[MAXN];
int cam;
struct bucket
{
    set<pair<int,int> >s;
    void compute()
    {

        auto it=s.end();
        //auto ptr=it;
        //ptr--;
        for(;;)
        {
            if(it==s.begin())
            {
                break;
            }
            --it;
            int t=(*it).first+cam+1;
            auto it1=s.lower_bound({t,-1});
            /*while((*ptr).first>=t)
            {
                if(ptr==s.begin())
                {
                    ptr--;
                    break;
                }
                ptr--;
            }
            ptr++;
            auto it1=ptr;*/
            if(it1==s.end())
            {
                dp1[(*it).second]=1;
                dp2[(*it).second]=t-1;
            }
            else
            {
                dp1[(*it).second]=dp1[(*it1).second]+1;
                dp2[(*it).second]=dp2[(*it1).second];
            }
        }
    }
}b[K];
int n;
int get_ans()
{
    int T=n/K+2;
    int lastb=(n-1)/T;
    int firstnz=-1;
    for(int i=0;i<=lastb;++i)
    {
        if(b[i].s.size()==0)continue;
        firstnz=i;
        break;
    }
    int t=(*b[firstnz].s.begin()).second;
    int last=dp2[t];
    int ret=dp1[t];
    //cout<<"starting from "<<t<<endl;
    for(int i=firstnz+1;i<=lastb;++i)
    {
        if(b[i].s.size()==0)continue;
        auto it=b[i].s.lower_bound({last+1,0});
        if(it==b[i].s.end())continue;
        last=dp2[(*it).second];
        ret+=dp1[(*it).second];
    }
    return ret;
}
void construct_whole()
{
    for(int i=0;i<K;++i)b[i].s.clear();
    vector<pair<int,int> >ve;
    for(int i=1;i<=n;++i)
    {
        ve.push_back({where[i],i});
    }
    sort(ve.begin(),ve.end());
    int T=n/K+2;
    for(int i=0;i<ve.size();++i)
    {
        where[ve[i].second]=ve[i].first;
        where1[ve[i].second]=i/T;
        b[i/T].s.insert(ve[i]);
    }
    for(int i=0;i<=(ve.size()-1)/T;++i)
    {
        b[i].compute();
    }
}
void init(int N, int L, int X[])
{
    n = N;
    cam = L;
    for(int i=0;i<N;++i)
    {
        where[i+1]=X[i];
    }
    construct_whole();
}
int cnt=0;
int update(int i, int y)
{
    i++;
    int j=where1[i];
    b[j].s.erase({where[i],i});
    int T=n/K+2;
    int lastb=(n-1)/T;
    int new_j=lastb;
    if((*b[1].s.begin()).first>y)
    {
        new_j=0;
    }
    else
    {
        for(int j=1;j<lastb;++j)
        {
            if((*b[j+1].s.begin()).first>y)
            {
                new_j=j;
                break;
            }
        }
    }
    b[new_j].s.insert({y,i});
    b[new_j].compute();
    where[i]=y;
    where1[i]=new_j;
    if(j!=new_j)b[j].compute();
    ++cnt;
    if(cnt%max(1,T-1)==0)
    {
        construct_whole();
    }
    return get_ans();
}

Compilation message (stderr)

elephants.cpp: In function 'void construct_whole()':
elephants.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=0;i<ve.size();++i)
      |                 ~^~~~~~~~~~
elephants.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<=(ve.size()-1)/T;++i)
      |                 ~^~~~~~~~~~~~~~~~~

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