oj.uz

Submission #200616

# Submission time Handle Problem Language Result Execution time Memory
200616 2020-02-07T15:38:58 Z gs18115 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5017 ms 12536 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 488 ms 2424 KB Output is correct
8 Correct 514 ms 2680 KB Output is correct
9 Correct 428 ms 4216 KB Output is correct
10 Correct 392 ms 4088 KB Output is correct
11 Correct 397 ms 3960 KB Output is correct
12 Correct 921 ms 4216 KB Output is correct
13 Correct 386 ms 3832 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 488 ms 2424 KB Output is correct
8 Correct 514 ms 2680 KB Output is correct
9 Correct 428 ms 4216 KB Output is correct
10 Correct 392 ms 4088 KB Output is correct
11 Correct 397 ms 3960 KB Output is correct
12 Correct 921 ms 4216 KB Output is correct
13 Correct 386 ms 3832 KB Output is correct
14 Correct 516 ms 3352 KB Output is correct
15 Correct 728 ms 3500 KB Output is correct
16 Correct 1794 ms 4728 KB Output is correct
17 Correct 1655 ms 5880 KB Output is correct
18 Correct 1759 ms 5756 KB Output is correct
19 Correct 602 ms 5880 KB Output is correct
20 Correct 1620 ms 5624 KB Output is correct
21 Correct 1461 ms 5688 KB Output is correct
22 Correct 587 ms 5368 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 488 ms 2424 KB Output is correct
8 Correct 514 ms 2680 KB Output is correct
9 Correct 428 ms 4216 KB Output is correct
10 Correct 392 ms 4088 KB Output is correct
11 Correct 397 ms 3960 KB Output is correct
12 Correct 921 ms 4216 KB Output is correct
13 Correct 386 ms 3832 KB Output is correct
14 Correct 516 ms 3352 KB Output is correct
15 Correct 728 ms 3500 KB Output is correct
16 Correct 1794 ms 4728 KB Output is correct
17 Correct 1655 ms 5880 KB Output is correct
18 Correct 1759 ms 5756 KB Output is correct
19 Correct 602 ms 5880 KB Output is correct
20 Correct 1620 ms 5624 KB Output is correct
21 Correct 1461 ms 5688 KB Output is correct
22 Correct 587 ms 5368 KB Output is correct
23 Correct 3040 ms 12408 KB Output is correct
24 Correct 3751 ms 12408 KB Output is correct
25 Correct 2081 ms 12408 KB Output is correct
26 Correct 2524 ms 12536 KB Output is correct
27 Correct 2652 ms 12408 KB Output is correct
28 Correct 2609 ms 5368 KB Output is correct
29 Correct 2447 ms 5284 KB Output is correct
30 Correct 2536 ms 5284 KB Output is correct
31 Correct 2425 ms 5320 KB Output is correct
32 Correct 2158 ms 11896 KB Output is correct
33 Correct 1678 ms 11232 KB Output is correct
34 Correct 2051 ms 12168 KB Output is correct
35 Correct 1904 ms 12408 KB Output is correct
36 Correct 1508 ms 11896 KB Output is correct
37 Correct 3278 ms 12408 KB Output is correct
38 Correct 2017 ms 11128 KB Output is correct
39 Correct 1869 ms 12280 KB Output is correct
40 Correct 2290 ms 11160 KB Output is correct
41 Correct 4876 ms 11896 KB Output is correct
42 Correct 5017 ms 12152 KB Output is correct