Submission #200616

#	Time	Username	Problem	Language	Result	Execution time	Memory
200616		gs18115	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	5017 ms	12536 KiB

elephants

#include "elephants.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
int sz=800;
int n,l;
int x[150010],gp[150010];
int ci[150010];
int pos[200][1310],pc[200][1310],np[200][1310];
int gn;
int gs[200];
inline void calc(int i)
{
    int k=gs[i];
    for(int j=gs[i];j-->0;)
    {
        while(x[pos[i][k-1]]>x[pos[i][j]]+l)
            k--;
        if(k==gs[i])
            np[i][j]=x[pos[i][j]]+l,pc[i][j]=1;
        else
            np[i][j]=np[i][k],pc[i][j]=pc[i][k]+1;
    }
    return;
}
inline void group()
{
    for(int i=0;i<gn;i++)
        gs[i]=0;
    gn=0;
    for(int i=0;i<n;i++)
        pos[gp[ci[i]]=i/sz][gs[i/sz]++]=ci[i],gn=i/sz+1;
    for(int i=0;i<gn;i++)
        calc(i);
    return;
}
inline void regroup()
{
    int ps=0;
    for(int i=0;i<gn;i++)
        for(int j=0;j<gs[i];j++)
            ci[ps++]=pos[i][j];
    group();
    return;
}
inline void del(int i)
{
    int g=gp[i];
    int j;
    for(j=0;j<gs[g];j++)
        if(pos[g][j]==i)
            break;
    gs[g]--;
    for(;j<gs[g];j++)
        pos[g][j]=pos[g][j+1];
    calc(g);
    return;
}
inline void ins(int i)
{
    int g;
    for(g=0;g<gn;g++)
        if(x[i]<=x[pos[g][gs[g]-1]])
            break;
    if(g==gn)
        g--;
    gp[i]=g;
    int j;
    for(j=0;j<gs[g];j++)
        if(x[i]<=x[pos[g][j]])
            break;
    for(int k=gs[g];k>j;k--)
        pos[g][k]=pos[g][k-1];
    gs[g]++;
    pos[g][j]=i;
    calc(g);
    return;
}
inline int calc()
{
    int d=-1;
    int ret=0;
    for(int i=0;i<gn;i++)
    {
        if(x[pos[i][gs[i]-1]]<=d)
            continue;
        int s=0;
        int e=gs[i]-1;
        while(s<e)
        {
            int m=s+e>>1;
            if(x[pos[i][m]]>d)
                e=m;
            else
                s=m+1;
        }
        ret+=pc[i][s];
        d=np[i][s];
    }
    return ret;
}
void init(int N,int L,int X[])
{
    n=N;
    l=L;
    for(int i=0;i<n;i++)
        x[i]=X[i],ci[i]=i;
    sort(ci,ci+n,[=](int&i,int&j){return x[i]<x[j];});
    group();
    return;
}
int cnt;
int update(int i, int y)
{
    if(++cnt%500==0)
        regroup();
    del(i);
    x[i]=y;
    ins(i);
    return calc();
}

Compilation message (stderr)

elephants.cpp: In function 'int calc()':
elephants.cpp:104:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int m=s+e>>1;
                   ~^~

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