oj.uz

Submission #1090083

# Submission time Handle Problem Language Result Execution time Memory
1090083 2024-09-17T17:19:58 Z onlk97 Comparing Plants (IOI20_plants) C++14
44 / 100
 349 ms 25040 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;
}
int sp;
set <int> d0,d1;
void init(int k,vector <int> r){
    n=r.size();
    if (k==2){
        sp=1;
        for (int i=0; i<n; i++){
            if (!r[i]) d0.insert(i);
            else d1.insert(i);
        }
        return;
    }
    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)+1,n,-1);
        }
        del_s(idx);
    }
}

int compare_plants(int x,int y){
    if (sp==1){
        auto it=d1.lower_bound(x);
        if (it==d1.end()||(*it)>=y) return 1;
        if ((d0.empty()||(*d0.begin()>=x))&&(d0.empty()||((*--d0.end())<y))) return 1;
        auto it2=d0.lower_bound(x);
        if (it2==d0.end()||(*it2)>=y) return -1;
        if ((d1.empty()||(*d1.begin()>=x))&&(d1.empty()||((*--d1.end())<y))) return 1;
        return 0;
    }
    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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 35 ms 4132 KB Output is correct
7 Incorrect 65 ms 6324 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 35 ms 5452 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2584 KB Output is correct
10 Correct 39 ms 5312 KB Output is correct
11 Correct 39 ms 5460 KB Output is correct
12 Correct 37 ms 5456 KB Output is correct
13 Correct 39 ms 5384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 35 ms 5452 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2584 KB Output is correct
10 Correct 39 ms 5312 KB Output is correct
11 Correct 39 ms 5460 KB Output is correct
12 Correct 37 ms 5456 KB Output is correct
13 Correct 39 ms 5384 KB Output is correct
14 Correct 54 ms 5892 KB Output is correct
15 Correct 274 ms 12020 KB Output is correct
16 Correct 54 ms 5888 KB Output is correct
17 Correct 242 ms 11840 KB Output is correct
18 Correct 343 ms 21232 KB Output is correct
19 Correct 146 ms 11848 KB Output is correct
20 Correct 250 ms 11840 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 33 ms 5368 KB Output is correct
4 Correct 225 ms 18240 KB Output is correct
5 Correct 252 ms 13276 KB Output is correct
6 Correct 273 ms 12096 KB Output is correct
7 Correct 300 ms 11848 KB Output is correct
8 Correct 253 ms 11844 KB Output is correct
9 Correct 270 ms 16704 KB Output is correct
10 Correct 246 ms 13468 KB Output is correct
11 Correct 97 ms 13572 KB Output is correct
12 Correct 131 ms 11840 KB Output is correct
13 Correct 349 ms 25040 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 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 348 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 35 ms 4132 KB Output is correct
7 Incorrect 65 ms 6324 KB Output isn't correct
8 Halted 0 ms 0 KB -