oj.uz

Submission #916255

# Submission time Handle Problem Language Result Execution time Memory
916255 2024-01-25T14:43:13 Z JakobZorz Dancing Elephants (IOI11_elephants) C++17
50 / 100
 733 ms 12808 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=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[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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 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 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8624 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 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 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8624 KB Output is correct
7 Correct 460 ms 9028 KB Output is correct
8 Correct 486 ms 9216 KB Output is correct
9 Correct 561 ms 12168 KB Output is correct
10 Correct 524 ms 12540 KB Output is correct
11 Correct 434 ms 12540 KB Output is correct
12 Correct 733 ms 11796 KB Output is correct
13 Correct 500 ms 12808 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 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 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8624 KB Output is correct
7 Correct 460 ms 9028 KB Output is correct
8 Correct 486 ms 9216 KB Output is correct
9 Correct 561 ms 12168 KB Output is correct
10 Correct 524 ms 12540 KB Output is correct
11 Correct 434 ms 12540 KB Output is correct
12 Correct 733 ms 11796 KB Output is correct
13 Correct 500 ms 12808 KB Output is correct
14 Incorrect 293 ms 9464 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 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 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8624 KB Output is correct
7 Correct 460 ms 9028 KB Output is correct
8 Correct 486 ms 9216 KB Output is correct
9 Correct 561 ms 12168 KB Output is correct
10 Correct 524 ms 12540 KB Output is correct
11 Correct 434 ms 12540 KB Output is correct
12 Correct 733 ms 11796 KB Output is correct
13 Correct 500 ms 12808 KB Output is correct
14 Incorrect 293 ms 9464 KB Output isn't correct
15 Halted 0 ms 0 KB -