oj.uz

Submission #916345

# Submission time Handle Problem Language Result Execution time Memory
916345 2024-01-25T17:31:46 Z JakobZorz Dancing Elephants (IOI11_elephants) C++17
100 / 100
 5653 ms 21496 KB 
#include"elephants.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
const int BUCKET_SIZE=256;
int 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=-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];
            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[]){
    int n=N;
    l=L;
    vector<int>vec;
    for(int i=0;i<n;i++){
        pos[i]=X[i];
        vec.push_back(pos[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--;
    while(cb&&buckets[cb]->arr.empty())
        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;
    }
    
    /*if(res==137){
        cout<<"special case\n";
        int c=-1;
        for(auto b:buckets){
            for(int a:b->arr){
                if(c>a){
                    cout<<"ERROR "<<c<<" "<<a<<"\n";
                }
                c=a;
            }
        }
    }*/
    return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 2 ms 8536 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 3 ms 8540 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 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 3 ms 8540 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 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 504 ms 9932 KB Output is correct
8 Correct 525 ms 9980 KB Output is correct
9 Correct 644 ms 13312 KB Output is correct
10 Correct 767 ms 14100 KB Output is correct
11 Correct 668 ms 13872 KB Output is correct
12 Correct 1395 ms 13464 KB Output is correct
13 Correct 620 ms 13720 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 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 504 ms 9932 KB Output is correct
8 Correct 525 ms 9980 KB Output is correct
9 Correct 644 ms 13312 KB Output is correct
10 Correct 767 ms 14100 KB Output is correct
11 Correct 668 ms 13872 KB Output is correct
12 Correct 1395 ms 13464 KB Output is correct
13 Correct 620 ms 13720 KB Output is correct
14 Correct 755 ms 11836 KB Output is correct
15 Correct 939 ms 10784 KB Output is correct
16 Correct 1716 ms 14344 KB Output is correct
17 Correct 1942 ms 15400 KB Output is correct
18 Correct 2090 ms 14112 KB Output is correct
19 Correct 1375 ms 14848 KB Output is correct
20 Correct 1939 ms 15116 KB Output is correct
21 Correct 2177 ms 14192 KB Output is correct
22 Correct 981 ms 14876 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 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 504 ms 9932 KB Output is correct
8 Correct 525 ms 9980 KB Output is correct
9 Correct 644 ms 13312 KB Output is correct
10 Correct 767 ms 14100 KB Output is correct
11 Correct 668 ms 13872 KB Output is correct
12 Correct 1395 ms 13464 KB Output is correct
13 Correct 620 ms 13720 KB Output is correct
14 Correct 755 ms 11836 KB Output is correct
15 Correct 939 ms 10784 KB Output is correct
16 Correct 1716 ms 14344 KB Output is correct
17 Correct 1942 ms 15400 KB Output is correct
18 Correct 2090 ms 14112 KB Output is correct
19 Correct 1375 ms 14848 KB Output is correct
20 Correct 1939 ms 15116 KB Output is correct
21 Correct 2177 ms 14192 KB Output is correct
22 Correct 981 ms 14876 KB Output is correct
23 Correct 4615 ms 19348 KB Output is correct
24 Correct 4987 ms 18680 KB Output is correct
25 Correct 3335 ms 18972 KB Output is correct
26 Correct 5170 ms 21496 KB Output is correct
27 Correct 5037 ms 19508 KB Output is correct
28 Correct 2779 ms 11756 KB Output is correct
29 Correct 2345 ms 11772 KB Output is correct
30 Correct 2726 ms 11856 KB Output is correct
31 Correct 2341 ms 12188 KB Output is correct
32 Correct 3379 ms 21116 KB Output is correct
33 Correct 2805 ms 20148 KB Output is correct
34 Correct 3797 ms 21064 KB Output is correct
35 Correct 1724 ms 21108 KB Output is correct
36 Correct 675 ms 20848 KB Output is correct
37 Correct 5320 ms 19428 KB Output is correct
38 Correct 3125 ms 19908 KB Output is correct
39 Correct 3910 ms 19368 KB Output is correct
40 Correct 2686 ms 20308 KB Output is correct
41 Correct 5653 ms 19920 KB Output is correct
42 Correct 5593 ms 19988 KB Output is correct