oj.uz

Submission #1090085

# Submission time Handle Problem Language Result Execution time Memory
1090085 2024-09-17T17:23:15 Z onlk97 Comparing Plants (IOI20_plants) C++14
44 / 100
 338 ms 25160 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 348 KB Output is correct
2 Correct 0 ms 348 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 388 KB Output is correct
6 Correct 34 ms 3072 KB Output is correct
7 Incorrect 66 ms 4164 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 35 ms 5456 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 35 ms 5460 KB Output is correct
11 Correct 36 ms 5464 KB Output is correct
12 Correct 35 ms 5456 KB Output is correct
13 Correct 35 ms 5456 KB Output is correct

Subtask #3
13.0 / 13.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 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 35 ms 5456 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 35 ms 5460 KB Output is correct
11 Correct 36 ms 5464 KB Output is correct
12 Correct 35 ms 5456 KB Output is correct
13 Correct 35 ms 5456 KB Output is correct
14 Correct 51 ms 5768 KB Output is correct
15 Correct 240 ms 12020 KB Output is correct
16 Correct 51 ms 5892 KB Output is correct
17 Correct 259 ms 11848 KB Output is correct
18 Correct 331 ms 21316 KB Output is correct
19 Correct 142 ms 11840 KB Output is correct
20 Correct 237 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 1 ms 2396 KB Output is correct
3 Correct 35 ms 5372 KB Output is correct
4 Correct 251 ms 18208 KB Output is correct
5 Correct 250 ms 13380 KB Output is correct
6 Correct 300 ms 12020 KB Output is correct
7 Correct 284 ms 12012 KB Output is correct
8 Correct 253 ms 11840 KB Output is correct
9 Correct 263 ms 16708 KB Output is correct
10 Correct 275 ms 13540 KB Output is correct
11 Correct 74 ms 13652 KB Output is correct
12 Correct 129 ms 11840 KB Output is correct
13 Correct 338 ms 25160 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 396 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 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 348 KB Output is correct
2 Correct 0 ms 348 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 388 KB Output is correct
6 Correct 34 ms 3072 KB Output is correct
7 Incorrect 66 ms 4164 KB Output isn't correct
8 Halted 0 ms 0 KB -