oj.uz

Submission #443738

# Submission time Handle Problem Language Result Execution time Memory
443738 2021-07-11T23:44:38 Z RGBB Dancing Elephants (IOI11_elephants) C++14
100 / 100
 3021 ms 7444 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//constants
const int MAXN=150000;
const int blk=500;
//important stuffs
int n,nb,l,cnt,arr[MAXN];
//elephant indices
int ind[MAXN];
//decomposition blocks
int pos[300][2*blk];
int val[300][2*blk];
int dis[300][2*blk];
//block sizes
int si[300];
//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();
}

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 0 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 0 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 0 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 371 ms 1360 KB Output is correct
8 Correct 377 ms 1484 KB Output is correct
9 Correct 277 ms 2680 KB Output is correct
10 Correct 308 ms 2628 KB Output is correct
11 Correct 240 ms 2732 KB Output is correct
12 Correct 547 ms 2684 KB Output is correct
13 Correct 282 ms 2684 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 0 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 371 ms 1360 KB Output is correct
8 Correct 377 ms 1484 KB Output is correct
9 Correct 277 ms 2680 KB Output is correct
10 Correct 308 ms 2628 KB Output is correct
11 Correct 240 ms 2732 KB Output is correct
12 Correct 547 ms 2684 KB Output is correct
13 Correct 282 ms 2684 KB Output is correct
14 Correct 281 ms 1776 KB Output is correct
15 Correct 476 ms 1964 KB Output is correct
16 Correct 913 ms 2908 KB Output is correct
17 Correct 927 ms 3736 KB Output is correct
18 Correct 1065 ms 3524 KB Output is correct
19 Correct 508 ms 3604 KB Output is correct
20 Correct 951 ms 3620 KB Output is correct
21 Correct 911 ms 3628 KB Output is correct
22 Correct 471 ms 3620 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 0 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 371 ms 1360 KB Output is correct
8 Correct 377 ms 1484 KB Output is correct
9 Correct 277 ms 2680 KB Output is correct
10 Correct 308 ms 2628 KB Output is correct
11 Correct 240 ms 2732 KB Output is correct
12 Correct 547 ms 2684 KB Output is correct
13 Correct 282 ms 2684 KB Output is correct
14 Correct 281 ms 1776 KB Output is correct
15 Correct 476 ms 1964 KB Output is correct
16 Correct 913 ms 2908 KB Output is correct
17 Correct 927 ms 3736 KB Output is correct
18 Correct 1065 ms 3524 KB Output is correct
19 Correct 508 ms 3604 KB Output is correct
20 Correct 951 ms 3620 KB Output is correct
21 Correct 911 ms 3628 KB Output is correct
22 Correct 471 ms 3620 KB Output is correct
23 Correct 2244 ms 7396 KB Output is correct
24 Correct 2506 ms 7356 KB Output is correct
25 Correct 1602 ms 7412 KB Output is correct
26 Correct 2112 ms 7364 KB Output is correct
27 Correct 2253 ms 7444 KB Output is correct
28 Correct 1174 ms 2244 KB Output is correct
29 Correct 1148 ms 2240 KB Output is correct
30 Correct 1199 ms 2236 KB Output is correct
31 Correct 1142 ms 2236 KB Output is correct
32 Correct 1341 ms 7348 KB Output is correct
33 Correct 1269 ms 7348 KB Output is correct
34 Correct 1665 ms 7348 KB Output is correct
35 Correct 1185 ms 7352 KB Output is correct
36 Correct 649 ms 7352 KB Output is correct
37 Correct 2293 ms 7424 KB Output is correct
38 Correct 1695 ms 7364 KB Output is correct
39 Correct 1743 ms 7416 KB Output is correct
40 Correct 1849 ms 7352 KB Output is correct
41 Correct 3021 ms 7356 KB Output is correct
42 Correct 3019 ms 7356 KB Output is correct