oj.uz

답안 #916251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916251 2024-01-25T14:36:46 Z JakobZorz 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 741 ms 12596 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()-1;
            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()-1;
        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={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[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.empty()&&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 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 458 ms 9188 KB Output is correct
8 Correct 520 ms 9068 KB Output is correct
9 Correct 552 ms 11700 KB Output is correct
10 Correct 522 ms 12536 KB Output is correct
11 Correct 439 ms 12544 KB Output is correct
12 Correct 741 ms 12028 KB Output is correct
13 Correct 491 ms 12596 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 458 ms 9188 KB Output is correct
8 Correct 520 ms 9068 KB Output is correct
9 Correct 552 ms 11700 KB Output is correct
10 Correct 522 ms 12536 KB Output is correct
11 Correct 439 ms 12544 KB Output is correct
12 Correct 741 ms 12028 KB Output is correct
13 Correct 491 ms 12596 KB Output is correct
14 Incorrect 294 ms 9460 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 458 ms 9188 KB Output is correct
8 Correct 520 ms 9068 KB Output is correct
9 Correct 552 ms 11700 KB Output is correct
10 Correct 522 ms 12536 KB Output is correct
11 Correct 439 ms 12544 KB Output is correct
12 Correct 741 ms 12028 KB Output is correct
13 Correct 491 ms 12596 KB Output is correct
14 Incorrect 294 ms 9460 KB Output isn't correct
15 Halted 0 ms 0 KB -