oj.uz

Submission #916258

# Submission time Handle Problem Language Result Execution time Memory
916258 2024-01-25T14:46:50 Z JakobZorz Dancing Elephants (IOI11_elephants) C++17
50 / 100
 772 ms 12288 KB 
#include"elephants.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
 
const int BUCKET_SIZE=256;
ll n,l;
ll pos[150000];
 
struct Bucket{
    vector<ll>arr;
    vector<ll>num;
    vector<ll>pos;
    
    void regen(){
        num.resize(arr.size());
        pos.resize(arr.size());
        for(int i=(int)arr.size()-1;i>=0;i--){
            num[i]=1;
            ll 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<ll,ll>get(ll 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.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.empty()&&buckets[cb]->arr[0]>=y)
            break;
        cb++;
    }
    if(cb)
        cb--;
    
    buckets[cb]->add(y);
    
    ll 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 1 ms 8540 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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 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 451 ms 9404 KB Output is correct
8 Correct 442 ms 9724 KB Output is correct
9 Correct 523 ms 10752 KB Output is correct
10 Correct 503 ms 12288 KB Output is correct
11 Correct 397 ms 12240 KB Output is correct
12 Correct 772 ms 11052 KB Output is correct
13 Correct 464 ms 12168 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 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 451 ms 9404 KB Output is correct
8 Correct 442 ms 9724 KB Output is correct
9 Correct 523 ms 10752 KB Output is correct
10 Correct 503 ms 12288 KB Output is correct
11 Correct 397 ms 12240 KB Output is correct
12 Correct 772 ms 11052 KB Output is correct
13 Correct 464 ms 12168 KB Output is correct
14 Incorrect 268 ms 10344 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 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 451 ms 9404 KB Output is correct
8 Correct 442 ms 9724 KB Output is correct
9 Correct 523 ms 10752 KB Output is correct
10 Correct 503 ms 12288 KB Output is correct
11 Correct 397 ms 12240 KB Output is correct
12 Correct 772 ms 11052 KB Output is correct
13 Correct 464 ms 12168 KB Output is correct
14 Incorrect 268 ms 10344 KB Output isn't correct
15 Halted 0 ms 0 KB -