oj.uz

Submission #443737

# Submission time Handle Problem Language Result Execution time Memory
443737 2021-07-11T23:37:08 Z RGBB Dancing Elephants (IOI11_elephants) C++17
100 / 100
 3556 ms 12388 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//constants
const int MAXN=150000;
const int blk=400;
//important stuffs
int n,nb,l,cnt,arr[MAXN];
//elephant indices
int ind[MAXN];
//decomposition blocks
int pos[375][2*blk];
int val[375][2*blk];
int dis[375][2*blk];
//block sizes
int si[375];
//actual code
void recalc(int p){
    if(si[p]==0)return;
    int pnt=si[p];
    for(int i=si[p]-1;i>=0;i--){
        while(pos[p][pnt-1]-l>pos[p][i])pnt--;
        if(pnt==si[p]){
            val[p][i]=1;
            dis[p][i]=pos[p][i]+l;
        }
        else{
            val[p][i]=val[p][pnt]+1;
            dis[p][i]=dis[p][pnt];
        }
    }
}
void reconstruct(){
    int tc=0;
    for(int i=0;i<nb;i++){
        for(int j=0;j<si[i];j++)arr[tc++]=pos[i][j];
    }
    for(int i=0;i<nb;i++){
        for(int j=0;j<blk&&i*blk+j<n;j++){
            pos[i][j]=arr[i*blk+j];
            si[i]=j+1;
        }
        recalc(i);
    }
}
void sub(int p,int v){
    int tc=0;
    while(pos[p][tc]!=v)tc++;
    for(int i=tc+1;i<si[p];i++)pos[p][i-1]=pos[p][i];
    si[p]--;
}
void add(int p,int v){
    int tc=si[p];
    while(tc>0&&pos[p][tc-1]>v){
        pos[p][tc]=pos[p][tc-1];
        tc--;
    }
    pos[p][tc]=v;
    si[p]++;
}
int query(){
    int ret=0;
    int cp=-1;
    for(int i=0;i<nb;i++){
        if(si[i]==0||pos[i][si[i]-1]<=cp)continue;
        int bp=(int*)lower_bound(pos[i],pos[i]+si[i],cp+1)-pos[i];
        ret+=val[i][bp];
        cp=dis[i][bp];
    }
    return ret;
}
void init(int N,int L,int X[]){
    n=N;
    l=L;
    nb=ceil((double)n/blk);
    cnt=0;
    for(int i=0;i<n;i++)ind[i]=X[i];
    for(int i=0;i<nb;i++){
        for(int j=0;j<blk&&i*blk+j<n;j++){
            pos[i][j]=X[i*blk+j];
            si[i]=j+1;
        }
        recalc(i);
    }
}
int update(int i,int y){
    cnt++;
    if(cnt%blk==0)reconstruct();
    int tc=0;
    while(si[tc]==0||pos[tc][0]>ind[i]||pos[tc][si[tc]-1]<ind[i])tc++;
    sub(tc,ind[i]);
    recalc(tc);
    tc=0;
    int prev=INT_MIN;
    while(tc<nb-1&&(si[tc]==0||prev>y||pos[tc][si[tc]-1]<y)){
        if(si[tc]!=0)prev=pos[tc][si[tc]-1];
        tc++;
    }
    add(tc,y);
    recalc(tc);
    ind[i]=y;
    return query();
}
void output(){
    for(int i=0;i<nb;i++){
        for(int y=0;y<si[i];y++)cout<<pos[i][y]<<" ";
        cout<<"\n";
    }
    for(int i=0;i<nb;i++){
        for(int y=0;y<si[i];y++)cout<<val[i][y]<<" ";
        cout<<"\n";
    }
    for(int i=0;i<nb;i++){
        for(int y=0;y<si[i];y++)cout<<dis[i][y]<<" ";
        cout<<"\n";
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 287 ms 2276 KB Output is correct
8 Correct 301 ms 2544 KB Output is correct
9 Correct 317 ms 4228 KB Output is correct
10 Correct 306 ms 4036 KB Output is correct
11 Correct 240 ms 4016 KB Output is correct
12 Correct 545 ms 4116 KB Output is correct
13 Correct 283 ms 3812 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 287 ms 2276 KB Output is correct
8 Correct 301 ms 2544 KB Output is correct
9 Correct 317 ms 4228 KB Output is correct
10 Correct 306 ms 4036 KB Output is correct
11 Correct 240 ms 4016 KB Output is correct
12 Correct 545 ms 4116 KB Output is correct
13 Correct 283 ms 3812 KB Output is correct
14 Correct 262 ms 3392 KB Output is correct
15 Correct 436 ms 3396 KB Output is correct
16 Correct 880 ms 4804 KB Output is correct
17 Correct 951 ms 5756 KB Output is correct
18 Correct 1050 ms 5584 KB Output is correct
19 Correct 501 ms 5700 KB Output is correct
20 Correct 937 ms 5628 KB Output is correct
21 Correct 936 ms 5616 KB Output is correct
22 Correct 484 ms 5112 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 287 ms 2276 KB Output is correct
8 Correct 301 ms 2544 KB Output is correct
9 Correct 317 ms 4228 KB Output is correct
10 Correct 306 ms 4036 KB Output is correct
11 Correct 240 ms 4016 KB Output is correct
12 Correct 545 ms 4116 KB Output is correct
13 Correct 283 ms 3812 KB Output is correct
14 Correct 262 ms 3392 KB Output is correct
15 Correct 436 ms 3396 KB Output is correct
16 Correct 880 ms 4804 KB Output is correct
17 Correct 951 ms 5756 KB Output is correct
18 Correct 1050 ms 5584 KB Output is correct
19 Correct 501 ms 5700 KB Output is correct
20 Correct 937 ms 5628 KB Output is correct
21 Correct 936 ms 5616 KB Output is correct
22 Correct 484 ms 5112 KB Output is correct
23 Correct 2781 ms 12384 KB Output is correct
24 Correct 2972 ms 12380 KB Output is correct
25 Correct 2253 ms 12388 KB Output is correct
26 Correct 2658 ms 12384 KB Output is correct
27 Correct 2730 ms 12356 KB Output is correct
28 Correct 986 ms 5188 KB Output is correct
29 Correct 995 ms 5188 KB Output is correct
30 Correct 986 ms 5180 KB Output is correct
31 Correct 958 ms 5188 KB Output is correct
32 Correct 1576 ms 11820 KB Output is correct
33 Correct 1559 ms 11140 KB Output is correct
34 Correct 2110 ms 12024 KB Output is correct
35 Correct 1471 ms 12240 KB Output is correct
36 Correct 689 ms 11824 KB Output is correct
37 Correct 2849 ms 12212 KB Output is correct
38 Correct 1945 ms 11076 KB Output is correct
39 Correct 2016 ms 12100 KB Output is correct
40 Correct 2151 ms 11048 KB Output is correct
41 Correct 3556 ms 11804 KB Output is correct
42 Correct 3549 ms 12040 KB Output is correct