oj.uz

Submission #1007645

# Submission time Handle Problem Language Result Execution time Memory
1007645 2024-06-25T09:43:24 Z Ahmed57 Comparing Plants (IOI20_plants) C++17
44 / 100
 770 ms 163352 KB 
#include "bits/stdc++.h"
#include "plants.h"

using namespace std;
#define int long long
pair<int,int> seg[800001];
int lazy[800001];
vector<int> arr;
void build(int p,int l,int r){
    if(l==r){
        seg[p] = {arr[l],l};
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
void prop(int p,int l,int r){
    seg[p].first+=lazy[p];
    if(l!=r){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
    }
    lazy[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,int val){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p]+=val;
        prop(p,l,r);
        return ;
    }
    if(r<lq||l>rq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val);
    update(p*2+1,md+1,r,lq,rq,val);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
pair<int,int> query(int p,int l,int r,int lq,int rq){
    prop(p,l,r);
    if(l>=lq&&r<=rq)return seg[p];
    if(r<lq||l>rq)return {1e9,0};
    int md = (l+r)/2;
    return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
int idx = 0,k,n;
vector<int> h;
int bad(int x){
    int l = x-k+1 , r = x-1;
    if(r==-1){
        l+=n;r+=n;
        pair<int,int> val = query(1,0,n-1,l,r);
        if(val.first==0)return val.second;
        return -1;
    }else{
        pair<int,int> val = query(1,0,n-1,max(0ll,l),r);
        if(l<0){
            l+=n;
            val = min(val,query(1,0,n-1,l,n-1));
        }
        if(val.first==0)return val.second;
        return -1;
    }
}
void fix(){
    pair<int,int> x = query(1,0,n-1,0,n-1);
    if(x.first<0){
        update(1,0,n-1,x.second,x.second,1e9);
    }else return ;
    fix();
}
void buld(int x){
    while(bad(x)!=-1){
        buld(bad(x));
    }
    int l = x-k+1 , r = x;
    update(1,0,n-1,max(0ll,l),r,-1);
    if(l<0){
        l+=n;
        update(1,0,n-1,l,n-1,-1);
    }
    h[x] = idx--;
    fix();
}
int li[200001][20];
int ri[200001][20];
int PL[200001][20];
int PR[200001][20];
void init(int32_t K, vector<int32_t> r){
    idx = r.size();
    n = r.size();
    k = K;
    for(int i = 0;i<n;i++){
        arr.push_back(r[i]);
        h.push_back(-1);
    }
    build(1,0,n-1);
    while(seg[1].first==0){
        buld(seg[1].second);
    }
    for(int i = 0;i<n;i++){
        if(h[i]==-1){
            assert(0);
        }
    }
    multiset<pair<int,int>> s;
    for(int i = 0;i<k-1;i++){
        s.insert({h[i],i});
    }
    for(int i = n-1;i>=0;i--){
        auto it = s.lower_bound(make_pair(h[i],0));
        if(it==s.begin()){
            ri[i][0] = 0;
            PR[i][0] = i;
        }else{
            it--;
            PR[i][0] = (*it).second;
            ri[i][0] = ((*it).second-i+n)%n;
        }
        int nah = (i+k-1)%n;
        s.erase(s.lower_bound(make_pair(h[nah],nah)));
        s.insert({h[i],i});
    }
    s.clear();
    for(int i = n-k+1;i<n;i++){
        s.insert({h[i],i});
    }
    for(int i = 0;i<n;i++){
        auto it = s.lower_bound(make_pair(h[i],0));
        if(it==s.begin()){
            li[i][0] = 0;
            PL[i][0] = i;
        }else{
            it--;
            PL[i][0] = (*it).second;
            li[i][0] = (i-(*it).second+n)%n;
        }
        int nah = (i-k+1+n)%n;
        s.erase(s.lower_bound(make_pair(h[nah],nah)));
        s.insert({h[i],i});
    }
    for(int j = 1;j<20;j++){
        for(int i = 0;i<n;i++){
            PL[i][j] = PL[PL[i][j-1]][j-1];
            PR[i][j] = PR[PR[i][j-1]][j-1];
            li[i][j] = li[i][j-1]+li[PL[i][j-1]][j-1];
            ri[i][j] = ri[i][j-1]+ri[PR[i][j-1]][j-1];
        }
    }
}
int32_t compare_plants(int32_t x, int32_t y){
    if(h[x]>h[y])return 1;
    return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Incorrect 1 ms 10588 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 3 ms 10792 KB Output is correct
7 Correct 44 ms 21972 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 43 ms 22012 KB Output is correct
11 Correct 39 ms 21852 KB Output is correct
12 Correct 38 ms 22096 KB Output is correct
13 Correct 43 ms 22100 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 3 ms 10792 KB Output is correct
7 Correct 44 ms 21972 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 43 ms 22012 KB Output is correct
11 Correct 39 ms 21852 KB Output is correct
12 Correct 38 ms 22096 KB Output is correct
13 Correct 43 ms 22100 KB Output is correct
14 Correct 94 ms 31276 KB Output is correct
15 Correct 749 ms 158644 KB Output is correct
16 Correct 86 ms 31184 KB Output is correct
17 Correct 690 ms 158496 KB Output is correct
18 Correct 430 ms 156600 KB Output is correct
19 Correct 450 ms 157364 KB Output is correct
20 Correct 718 ms 163352 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 42 ms 15580 KB Output is correct
4 Correct 308 ms 150456 KB Output is correct
5 Correct 365 ms 150432 KB Output is correct
6 Correct 517 ms 150544 KB Output is correct
7 Correct 608 ms 151096 KB Output is correct
8 Correct 770 ms 156344 KB Output is correct
9 Correct 358 ms 150224 KB Output is correct
10 Correct 370 ms 150444 KB Output is correct
11 Correct 305 ms 150196 KB Output is correct
12 Correct 335 ms 150364 KB Output is correct
13 Correct 443 ms 154036 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Incorrect 2 ms 10584 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Incorrect 1 ms 10676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Incorrect 1 ms 10588 KB Output isn't correct
5 Halted 0 ms 0 KB -