oj.uz

Submission #18016

# Submission time Handle Problem Language Result Execution time Memory
18016 2016-01-18T08:18:46 Z comet Dancing Elephants (IOI11_elephants) C++
100 / 100
 8537 ms 22608 KB 
#include <cstdio>
#include <algorithm>
using namespace std;
 
int N,M,L;
int B=500;
 
struct group{
    int sz,p[1010],cnt[1010],nxt[1010];
    void init(){
        int id=sz-1;
        for(int i=sz-1;i>=0;i--){
            if(p[sz-1]-p[i]<=L)cnt[i]=1,nxt[i]=p[i]+L+1;
            else{
                while(p[id]-p[i]>L)id--;
                cnt[i]=cnt[id+1]+1;
                nxt[i]=nxt[id+1];
            }
        }
    }
    void push(int x){
        int id=0;
        while(id<sz&&p[id]<=x)id++;
        sz++;
        for(int i=sz-1;i>id;i--)p[i]=p[i-1];
        p[id]=x;
        init();
    }
    void pop(int x){
        int id=0;
        while(p[id]<=x)id++;
        for(int i=id;i<sz;i++)p[i-1]=p[i];
        sz--;
        init();
    }
}a[300];
 
struct elephant{
    int p,group_id,id;
    bool operator<(const elephant& r)const{
        return p<r.p;
    }
}b[150010];
 
int ID[150010];
 
void renewal(){
    sort(b,b+N);
    for(int i=0;i<M;i++)a[i].sz=0;
    for(int i=0;i<N;i++){
        ID[b[i].id]=i;
        b[i].group_id=i/B;
        a[i/B].p[a[i/B].sz++]=b[i].p;
        M=max(M,i/B+1);
    }
    for(int i=0;i<M;i++){
        a[i].init();
    }
}
 
void init(int N_, int L_, int X[]){
    N=N_;
    L=L_;
    for(int i=0;i<N;i++)b[i]=elephant{X[i],i/B,i};
    renewal();
}
 
int findGroup(int x){
    if(a[0].p[0]>x)return 0;
    for(int i=0;i<M-1;i++){
        if(a[i].p[0]<=x&&x<a[i+1].p[0])return i;
    }
    return M-1;
}
 
int calc(){
    int x=0,ret=0;
    for(int i=0;i<M;i++){
        int id=lower_bound(a[i].p,a[i].p+a[i].sz,x)-a[i].p;
        if(id==a[i].sz)continue;
        ret+=a[i].cnt[id];
        x=a[i].nxt[id];
    }
    return ret;
}
 
int update(int i, int y){
    int id=b[ID[i]].group_id;
    a[id].pop(b[ID[i]].p);
    b[ID[i]].p=y;
 	if(a[id].sz==0){
 		renewal();
 		return calc();
 	}
    id=b[ID[i]].group_id=findGroup(y);
    a[id].push(y);
    if(a[id].sz>1000)renewal();
    return calc();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 22608 KB Output is correct
2 Correct 377 ms 22608 KB Output is correct
3 Correct 431 ms 22608 KB Output is correct
4 Correct 982 ms 22608 KB Output is correct
5 Correct 956 ms 22608 KB Output is correct
6 Correct 714 ms 22608 KB Output is correct
7 Correct 975 ms 22608 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 22608 KB Output is correct
2 Correct 569 ms 22608 KB Output is correct
3 Correct 1111 ms 22608 KB Output is correct
4 Correct 1118 ms 22608 KB Output is correct
5 Correct 1213 ms 22608 KB Output is correct
6 Correct 1933 ms 22608 KB Output is correct
7 Correct 1107 ms 22608 KB Output is correct
8 Correct 1074 ms 22608 KB Output is correct
9 Correct 1846 ms 22608 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2429 ms 22608 KB Output is correct
2 Correct 2597 ms 22608 KB Output is correct
3 Correct 1954 ms 22608 KB Output is correct
4 Correct 8537 ms 22608 KB Output is correct
5 Correct 8473 ms 22608 KB Output is correct
6 Correct 2306 ms 22608 KB Output is correct
7 Correct 2125 ms 22608 KB Output is correct
8 Correct 2324 ms 22608 KB Output is correct
9 Correct 2111 ms 22608 KB Output is correct
10 Correct 8280 ms 22608 KB Output is correct
11 Correct 5262 ms 22608 KB Output is correct
12 Correct 8172 ms 22608 KB Output is correct
13 Correct 5590 ms 22608 KB Output is correct
14 Correct 3626 ms 22608 KB Output is correct
15 Correct 2364 ms 22608 KB Output is correct
16 Correct 8275 ms 22608 KB Output is correct
17 Correct 8257 ms 22608 KB Output is correct
18 Correct 8252 ms 22608 KB Output is correct
19 Correct 3041 ms 22608 KB Output is correct
20 Correct 3057 ms 22608 KB Output is correct