Submission #1132152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132152		StefanSebez	Comparing Plants (IOI20_plants)	C++20	27 / 100	4091 ms	13584 KiB

plants

#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=2e5+50,inf=1e8;
int k,n;
int pref[2*N],r[2*N],a[N];
int Plus(int i,int x){i+=x;while(i<1)i+=n;while(i>n)i-=n;return i;}
int suma(int l,int r){
    if(l<=r) return pref[r]-pref[l-1];
    return pref[r+n]-pref[l-1];
}
int dist(int l,int r){
    if(l<=r) return r-l+1;
    return n+(r-l+1);
}
struct SegTree{
    int root,nc,lc[2*N],rc[2*N],mn[2*N],lazy[2*N];
    SegTree(){mn[0]=inf;}
    void update(int &c,int x){if(!c)c=++nc;mn[c]+=x;lazy[c]+=x;}
    void push(int c){update(lc[c],lazy[c]),update(rc[c],lazy[c]),lazy[c]=0;}
    void Update(int &c,int ss,int se,int qs,int qe,int qval){
        if(!c)c=++nc;
        if(qs>qe||se<qs||qe<ss)return;
        if(qs<=ss&&se<=qe){update(c,qval);return;}
        int mid=ss+se>>1;push(c);
        Update(lc[c],ss,mid,qs,qe,qval),Update(rc[c],mid+1,se,qs,qe,qval);
        mn[c]=min(mn[lc[c]],mn[rc[c]]);
    }
    /*void Update(int &c,int ss,int se,int qind,int qval){
        if(!c)c=++nc;
        if(ss==se){mn[c]+=qval;return;}
        int mid=ss+se>>1;
        if(qind<=mid)Update(lc[c],ss,mid,qind,qval);
        else Update(rc[c],mid+1,se,qind,qval);
        mn[c]=min(mn[lc[c]],mn[rc[c]]);
    }*/
    int Get(int c,int ss,int se,int qs,int qe){
        if(qs>qe||se<qs||qe<ss)return inf;
        if(qs<=ss&&se<=qe)return mn[c];
        int mid=ss+se>>1;push(c);
        return min(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
    }
}ST;
void init(int k1, std::vector<int> r1){
    k=k1;n=r1.size();
    for(int i=1;i<=n;i++) r[i]=r1[i-1];
    for(int i=n+1;i<=2*n;i++) r[i]=r[i-n];
    bool was[n+10]={false};
    for(int i=1;i<=n;i++) ST.Update(ST.root,1,n,i,i,r[i]);
    vector<int>nule;for(int i=1;i<=n;i++) if(r[i]==0) nule.pb(i);
    for(int c=n;c>=1;c--){
        int ind=0,maks=0,idx=0;
        for(int i=1;i<=0;i++){
            if(was[i]||ST.Get(ST.root,1,n,i,i)!=0) continue;
            int nesto=inf;
            /*for(int j=Plus(i,-1),ct=k-1;ct--;j=Plus(j,-1)){
                if(was[j]) continue;
                nesto=min(nesto,r[j]);
            }*/
            int levo=Plus(i,-k+1),desno=Plus(i,-1);
            if(levo<=desno) nesto=ST.Get(ST.root,1,n,levo,desno);
            else nesto=min(ST.Get(ST.root,1,n,1,desno),ST.Get(ST.root,1,n,levo,n));
            //printf("*%i\n",nesto);
            if(nesto>maks){
                maks=nesto,ind=i;
            }
        }
        while(ind<n){
            int l=ind+1,r=n,ind1;
            while(l<=r){
                int mid=l+r>>1;
                int x=ST.Get(ST.root,1,n,ind+1,mid);
                if(x==0) ind1=mid,r=mid-1;
                else l=mid+1;
            }
            ind=ind1;
            int nesto=inf;
            int levo=Plus(ind,-k+1),desno=Plus(ind,-1);
            if(levo<=desno) nesto=ST.Get(ST.root,1,n,levo,desno);
            else nesto=min(ST.Get(ST.root,1,n,1,desno),ST.Get(ST.root,1,n,levo,n));
            if(nesto>0) break;
        }
        //printf("%i\n",ind);
        //swap(nule[idx],nule.back());
        //nule.pop_back();
        a[ind]=c;
        was[ind]=true;
        /*for(int j=Plus(ind,-1),ct=k-1;ct--;j=Plus(j,-1)){
            if(was[j]) continue;
            r[j]--;if(r[j]==0) nule.pb(j);
            ST.Update(ST.root,1,n,j,-1);
        }*/
        int levo=Plus(ind,-k+1),desno=Plus(ind,-1);
        if(levo<=desno) ST.Update(ST.root,1,n,levo,desno,-1);
        else ST.Update(ST.root,1,n,1,desno,-1),ST.Update(ST.root,1,n,levo,n,-1);
        ST.Update(ST.root,1,n,ind,ind,inf);
        //for(int i=1;i<=n;i++) printf("%i ",r[i]);printf("\n");
    }
    //for(int i=1;i<=n;i++) printf("%i ",a[i]);printf("\n");
}
int compare_plants(int x, int y){
    x++,y++;
    if(a[x]>a[y]) return 1;
    if(a[x]<a[y]) return -1;
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25