oj.uz

Submission #1090073

# Submission time Handle Problem Language Result Execution time Memory
1090073 2024-09-17T17:04:03 Z onlk97 Comparing Plants (IOI20_plants) C++14
17 / 100
 352 ms 33604 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

int n;
pair <int,int> seg[800040];
int laz[800040],arr[200010];
void build(int id,int tl,int tr){
    if (tl==tr){
        seg[id]={arr[tl],tl};
        return;
    }
    int tm=(tl+tr)/2;
    build(2*id,tl,tm);
    build(2*id+1,tm+1,tr);
    seg[id]=min(seg[2*id],seg[2*id+1]);
}
void pushdown(int id,int tl,int tr){
    seg[2*id].first+=laz[id]; laz[2*id]+=laz[id];
    seg[2*id+1].first+=laz[id]; laz[2*id+1]+=laz[id];
    laz[id]=0;
}
void update(int id,int tl,int tr,int l,int r,int val){
    if (l>r) return;
    if (l<=tl&&tr<=r){
        seg[id].first+=val;
        laz[id]+=val;
        return;
    }
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    update(2*id,tl,tm,l,min(r,tm),val);
    update(2*id+1,tm+1,tr,max(l,tm+1),r,val);
    seg[id]=min(seg[2*id],seg[2*id+1]);
}
pair <int,int> query(int id,int tl,int tr,int l,int r){
    if (l>r) return {1e9,1e9};
    if (l<=tl&&tr<=r) return seg[id];
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    pair <int,int> lx=query(2*id,tl,tm,l,min(r,tm));
    pair <int,int> rx=query(2*id+1,tm+1,tr,max(l,tm+1),r);
    return min(lx,rx);
}
vector <int> p;
set <int> s;
set <pair <int,int>,greater <pair <int,int> > > diff;
void add_s(int u){
    if (s.empty()){
        s.insert(u);
        return;
    }
    if (s.size()==1){
        int prv=*s.begin();
        s.insert(u);
        if (prv>u) swap(prv,u);
        diff.insert({u-prv,u});
        diff.insert({prv-u+n,prv});
        return;
    }
    auto it=s.lower_bound(u);
    if (it==s.end()) it=s.begin();
    int nxt=(*it);
    if (it==s.begin()) it=s.end();
    it--;
    int prv=(*it);
    diff.erase({(nxt>prv?nxt-prv:nxt-prv+n),nxt});
    diff.insert({(u>prv?u-prv:u-prv+n),u});
    diff.insert({(nxt>u?nxt-u:nxt-u+n),nxt});
    s.insert(u);
}
void del_s(int u){
    if (s.size()<=2){
        s.erase(u);
        diff.clear();
        return;
    }
    auto it=s.lower_bound(u);
    auto it2=it;
    it2++;
    if (it2==s.end()) it2=s.begin();
    int nxt=(*it2);
    it2=it;
    if (it2==s.begin()) it2=(--s.end());
    else it2--;
    int prv=(*it2);
    diff.erase({(u>prv?u-prv:u-prv+n),u});
    diff.erase({(nxt>u?nxt-u:nxt-u+n),nxt});
    diff.insert({(nxt>prv?nxt-prv:nxt-prv+n),nxt});
    s.erase(u);
}
int get_s(){
    if (s.size()==1) return *s.begin();
    pair <int,int> tp=*diff.begin();
    return tp.second;
}
void init(int k,vector <int> r){
    n=r.size();
    r.insert(r.begin(),0);
    p.resize(n+1);
    for (int i=1; i<=n; i++) arr[i]=r[i];
    build(1,1,n);
    for (int i=n; i; i--){
        while (1){
            pair <int,int> tp=query(1,1,n,1,n);
            if (tp.first) break;
            add_s(tp.second);
            update(1,1,n,tp.second,tp.second,1e9);
        }
        int idx=get_s();
        p[idx]=i;
        if (idx>=k) update(1,1,n,idx-k+1,idx,-1);
        else {
            update(1,1,n,1,idx,-1);
            update(1,1,n,n-(k-idx)+2,n,-1);
        }
        del_s(idx);
    }
}

int compare_plants(int x,int y){
    x++; y++;
    if (p[x]>p[y]) return 1;
    return -1;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 39 ms 4944 KB Output is correct
4 Correct 238 ms 21188 KB Output is correct
5 Correct 284 ms 16452 KB Output is correct
6 Correct 309 ms 15328 KB Output is correct
7 Correct 328 ms 15532 KB Output is correct
8 Correct 295 ms 15684 KB Output is correct
9 Correct 265 ms 19652 KB Output is correct
10 Correct 259 ms 16452 KB Output is correct
11 Correct 352 ms 33604 KB Output is correct
12 Correct 134 ms 15176 KB Output is correct
13 Correct 329 ms 28232 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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