oj.uz

답안 #18008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18008 2016-01-18T08:10:09 Z comet 코끼리 (Dancing Elephants) (IOI11_elephants) C++
97 / 100
 9000 ms 23792 KB 
#include <cstdio>
#include <algorithm>
using namespace std;
 
int N,M,L,Q;
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[400];
 
struct elephant{
    int p,group_id,id;
    bool operator<(const elephant& r)const{
        return p<r.p;
    }
}b[150010];
 
int ID[150010];
 
void renewal(){
	Q=0;
    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){
	Q++;
    int id=b[ID[i]].group_id;
    a[id].pop(b[ID[i]].p);
    b[ID[i]].p=y;
 
    id=b[ID[i]].group_id=findGroup(y);
    a[id].push(y);
    if(Q>=490)renewal();
    return calc();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 23792 KB Output is correct
2 Correct 0 ms 23792 KB Output is correct
3 Correct 0 ms 23792 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 23792 KB Output is correct
2 Correct 0 ms 23792 KB Output is correct
3 Correct 0 ms 23792 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 501 ms 23792 KB Output is correct
2 Correct 534 ms 23792 KB Output is correct
3 Correct 581 ms 23792 KB Output is correct
4 Correct 992 ms 23792 KB Output is correct
5 Correct 975 ms 23792 KB Output is correct
6 Correct 1123 ms 23792 KB Output is correct
7 Correct 987 ms 23792 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 595 ms 23792 KB Output is correct
2 Correct 827 ms 23792 KB Output is correct
3 Correct 1629 ms 23792 KB Output is correct
4 Correct 1907 ms 23792 KB Output is correct
5 Correct 2060 ms 23792 KB Output is correct
6 Correct 1970 ms 23792 KB Output is correct
7 Correct 1924 ms 23792 KB Output is correct
8 Correct 1965 ms 23792 KB Output is correct
9 Correct 1870 ms 23792 KB Output is correct

Subtask #5
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4094 ms 23792 KB Output is correct
2 Correct 4339 ms 23792 KB Output is correct
3 Correct 3397 ms 23792 KB Output is correct
4 Execution timed out 9000 ms 23792 KB Program timed out
5 Halted 0 ms 0 KB -