Submission #1291777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291777		lambd47	Comparing Plants (IOI20_plants)	C++20	In queue	0 ms	0 KiB

plants

#include<bits/stdc++.h>
#include "plants.h"

using namespace std;
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()

const int MX=1e5+7;
pair<int,int> seg[4*MX];//maximo
int lz[4*MX];
void refresh(int pos, int ini, int fim){
    if(lz[pos]==0)return;
    seg[pos].first+=lz[pos];
    if(ini==fim){
        lz[pos]=0;return;
    }
    lz[2*pos]+=lz[pos];
    lz[2*pos+1]+=lz[pos];
    lz[pos]=0;
    return;
}
pair<int,int> merge(pair<int,int> a, pair<int,int> b){
    if(a.first==b.first)return make_pair(a.first,min(a.second,b.second));
    else if(a.first>b.first)return a;
    else return b;
}
void update(int pos, int ini, int fim, int l, int r,int val){
    refresh(pos,ini,fim);
    if(ini>r || fim<l)return;
    if(l<= ini && fim<=r){
        lz[pos]+=val;
        refresh(pos,ini,fim);
        return;
    }
    int m=(ini+fim)/2;
    int e=2*pos,d=2*pos+1;
    update(e,ini,m,l,r,val);
    update(d,m+1,fim,l,r,val);
    seg[pos]=merge(seg[e],seg[d]);
}
pair<int,int> query(int pos, int ini, int fim, int l, int r){
    refresh(pos,ini,fim);
    if(ini>r || fim<l)return {-1,-1};
    if(l<= ini && fim<=r)return seg[pos];
    int m=(ini+fim)/2;
    return merge(query(2*pos,ini,m,l,r),query(2*pos+1,m+1,fim,l,r));
}
vector<int> val;
int n;
int k;
pair<int,int> build(int pos, int ini, int fim){
    if(ini==fim){
        return seg[pos]={val[ini],ini};
    }
    int m=(ini+fim)/2;
    return seg[pos]=merge(build(2*pos,ini,m),build(2*pos+1,m+1,fim));
}
vector<int> ord;
int nxt2(int id){
    if(id+k-1>n-1){
        int x=id+k-1-n+1;
        pair<int,int> p=query(1,0,n-1,id+1,n-1);
        if(p.first==k-1)return p.second;
        p=query(1,0,n-1,0,x-1);
        if(p.first==k-1)return p.second;
        return -1;
    }
    else{
        pair<int,int> p=query(1,0,n-1,id+1,id+k-1);
        if(p.first==k-1)return p.second;
        else return -1;
    }
}
int nxt(int id){
    int mx=k-1;
    pair<int,int> p=query(1,0,n-1,id+1,n-1);
    if(p.first==mx)return p.second;
    p=query(1,0,n-1,0,id-1);
    if(p.first==mx)return p.second;
    return -1;
}
pair<int,int> getlst(int id){
    if(id>=k-1){
        return query(1,0,n-1,id-k+1,id-1);
    }
    else{
        int x=k-1-id;//vou ter que updatear esses x caras na frente
        if(query(1,0,n-1,n-1-x+1,n-1).first!=k-1)return query(1,0,n-1,0,id-1);
        else return query(1,0,n-1,n-1-x+1,n-1);
    }
}
void updlst(int id){
    if(id>=k-1){
        update(1,0,n-1,id-k+1,id-1,1);
    }
    else{
        int x=k-1-id;//vou ter que updatear esses x caras na frente
        update(1,0,n-1,0,id-1,1);
        update(1,0,n-1,n-1-x+1,n-1,1);
    }
}

void init(int kk, std::vector<int> vec) {
    k=kk;
    n=sz(vec);
    val=vec;
    ord.resize(n);
    build(1,0,n-1);
    int goat=0;
    vector<bool> marc(n,0);
    L(i,0,n-1){
        if(vec[i]==k-1){
            goat=i;
            int a=nxt2(i);
            if(a!=-1)marc[a]=1;
        }
    }
    L(i,0,n-1){
        if(vec[i]==k-1 && marc[i]==0)goat=i;
    }
    int at=n;
    const int MOD=1e9;

    while(at>0){
        if(goat==-1)return;
        ord[goat]=at;
        update(1,0,n-1,goat,goat,-MOD);
        goat=nxt(goat);
        while(getlst(goat).first==k-1)goat=getlst(goat).second;
        at--;
    }
    //L(i,0,n-1)cout<<ord[i];
}

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