Submission #1090083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090083		onlk97	Comparing Plants (IOI20_plants)	C++14	44 / 100	349 ms	25040 KiB

plants

#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
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25