oj.uz

답안 #916267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916267 2024-01-25T14:54:38 Z JakobZorz 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 756 ms 12544 KB 
#include"elephants.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
const int BUCKET_SIZE=256;
int n,l;
int pos[150000];
 
struct Bucket{
    vector<int>arr;
    vector<int>num;
    vector<int>pos;
    
    void regen(){
        num.resize(arr.size());
        pos.resize(arr.size());
        for(int i=(int)arr.size()-1;i>=0;i--){
            num[i]=1;
            int p=arr[i]+l;
            if(p>=arr.back()){
                pos[i]=p;
                continue;
            }
            
            int l=i-1,r=(int)arr.size();
            while(l<r-1){
                int m=(l+r)/2;
                if(arr[m]<=p)
                    l=m;
                else
                    r=m;
            }
            num[i]=num[r]+1;
            pos[i]=pos[r];
        }
    }
    
    void erase(int el){
        auto it=lower_bound(arr.begin(),arr.end(),el);
        arr.erase(it);
        
        regen();
    }
    
    void add(int el){
        auto it=upper_bound(arr.begin(),arr.end(),el);
        arr.insert(it,el);
        
        regen();
    }
    
    pair<int,int>get(int p){
        if(arr.empty()||p>=arr.back())
            return{0,p};
        
        int l=-1,r=(int)arr.size();
        while(l<r-1){
            int m=(l+r)/2;
            if(arr[m]<=p)
                l=m;
            else
                r=m;
        }
        
        return{num[r],pos[r]};
    }
};
 
vector<Bucket*>buckets;
 
void init(int N,int L,int X[]){
    n=N;
    l=L;
    vector<int>vec;
    for(int i=0;i<n;i++){
        pos[i]=X[i];
        vec.push_back(X[i]);
    }
    sort(vec.begin(),vec.end());
    buckets.push_back(new Bucket);
    for(int i:vec){
        buckets.back()->arr.push_back(i);
        if((int)buckets.back()->arr.size()>=BUCKET_SIZE){
            buckets.push_back(new Bucket);
        }
    }
    
    for(auto i:buckets)
        i->regen();
}
 
int update(int i,int y){
    // balance buckets
    for(int i=0;i<(int)buckets.size();i++){
        if(buckets[i]->arr.size()>=2*BUCKET_SIZE){
            buckets.insert(buckets.begin()+i+1,new Bucket);
            buckets[i+1]->arr=vector<int>(buckets[i]->arr.begin()+buckets[i]->arr.size()/2,buckets[i]->arr.end());
            buckets[i]->arr.erase(buckets[i]->arr.begin()+buckets[i]->arr.size()/2,buckets[i]->arr.end());
            buckets[i]->regen();
            buckets[i+1]->regen();
        }
    }
    
    for(auto b:buckets){
        if(b->arr.size()&&b->arr[0]<=pos[i]&&pos[i]<=b->arr.back()){
            b->erase(pos[i]);
            break;
        }
    }
    pos[i]=y;
    
    int cb=0;
    while(cb<(int)buckets.size()){
        if(buckets[cb]->arr.size()&&buckets[cb]->arr[0]>y)
            break;
        cb++;
    }
    if(cb)
        cb--;
    
    buckets[cb]->add(y);
    
    int pos=-1,res=0;
    
    for(auto b:buckets){
        auto r=b->get(pos);
        res+=r.first;
        pos=r.second;
    }
    
    return res;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 515 ms 8796 KB Output is correct
8 Correct 497 ms 8996 KB Output is correct
9 Correct 543 ms 11628 KB Output is correct
10 Correct 513 ms 12544 KB Output is correct
11 Correct 468 ms 12512 KB Output is correct
12 Correct 756 ms 11780 KB Output is correct
13 Correct 507 ms 12420 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 515 ms 8796 KB Output is correct
8 Correct 497 ms 8996 KB Output is correct
9 Correct 543 ms 11628 KB Output is correct
10 Correct 513 ms 12544 KB Output is correct
11 Correct 468 ms 12512 KB Output is correct
12 Correct 756 ms 11780 KB Output is correct
13 Correct 507 ms 12420 KB Output is correct
14 Incorrect 425 ms 9796 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 515 ms 8796 KB Output is correct
8 Correct 497 ms 8996 KB Output is correct
9 Correct 543 ms 11628 KB Output is correct
10 Correct 513 ms 12544 KB Output is correct
11 Correct 468 ms 12512 KB Output is correct
12 Correct 756 ms 11780 KB Output is correct
13 Correct 507 ms 12420 KB Output is correct
14 Incorrect 425 ms 9796 KB Output isn't correct
15 Halted 0 ms 0 KB -