Submission #521871

#	Time	Username	Problem	Language	Result	Execution time	Memory
521871		A_D	Comparing Plants (IOI20_plants)	C++14	0 / 100	1 ms	300 KiB

plants

#include "plants.h"

#include <bits/stdc++.h>
using namespace std;
const int NN=2e5+100;
int a[NN];
int seg[4*NN];
int lazy[4*NN];
int nn;
vector<int> vec;
void fix(int p,int s,int e)
{
    seg[p]+=lazy[p];
    if(s!=e){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
    }
    lazy[p]=0;
}
void update(int p,int s,int e,int a,int b,int v)
{
    fix(p,s,e);
    if(a<=s&&e<=b){
        lazy[p]+=v;
        fix(p,s,e);
        return;
    }
    if(a>e||b<s)return;
    int mid=(s+e)/2;
    update(p*2,s,mid,a,b,v);
    update(p*2+1,mid+1,e,a,b,v);
    seg[p]=min(seg[p*2],seg[p*2+1]);
}
int get(int p,int s,int e)
{
    fix(p,s,e);
    if(s==e){
        return s;
    }
    int mid=(s+e)/2;
    fix(p*2,s,mid);
    if(seg[p*2]==0){
        return get(p*2,s,mid);
    }
    else{
        return get(p*2+1,mid+1,e);
    }
}
void get2(int p,int s,int e,int a,int b)
{
    fix(p,s,e);
    if(seg[p]!=0||s>b||e<a)return ;
    if(s==e){
        vec.push_back(s);
        return;
    }
    int mid=(s+e)/2;
    get2(p*2,s,mid,a,b);
    get2(p*2+1,mid+1,e,a,b);
}
void upd(int a,int b,int v)
{
    if(a<=b){
        update(1,0,nn-1,a,b,v);
        if(v<0)get2(1,0,nn-1,a,b);
    //    cout<<a<<" "<<b<<" "<<v<<endl;
    }
    else{
        update(1,0,nn-1,a,nn-1,v);
        if(v<0)get2(1,0,nn-1,a,nn-1);
        update(1,0,nn-1,0,b,v);
        if(v<0)get2(1,0,nn-1,0,b);
  //      cout<<a<<" "<<nn-1<<" "<<v<<endl;
//        cout<<0<<" "<<b<<" "<<v<<endl;
    }
}
void build(int p,int s,int e)
{
    fix(p,s,e);
    if(s==e){
//        cout<<"s "<<s<<" "<<seg[p]<<endl;
        return;
    }
    int mid=(s+e)/2;
    build(p*2,s,mid);
    build(p*2+1,mid+1,e);
}
void init(int k,vector<int> r){
    nn=r.size();
    int cnt=nn;
    for(int i=0;i<nn;i++){
        upd(i,i,r[i]);
        if(r[i]==0){
            int ll=(i+1)%nn;
            int rr=(i+k-1+nn)%nn;
            upd(ll,rr,+1);
//            cout<<ll<<" "<<rr<<" "<<+1<<endl;
        }
    }
    while(seg[1]==0){
        vec.clear();
      //  build(1,0,nn-1);
        int i=get(1,0,nn-1);
        a[i]=cnt--;
        upd(i,i,1e8);
        int ll=(i+1)%nn;
        int rr=(i+k-1+nn)%nn;
        upd(ll,rr,-1);
  //      cout<<ll<<" "<<rr<<" "<<-1<<endl;
        rr=(i-1+nn)%nn;
        ll=(i-k+1+nn)%nn;
        upd(ll,rr,-1);
        for(auto x:vec){
            upd(x+1,(x+k-1+nn)%nn,1);
        }
      //  cout<<ll<<" "<<rr<<" "<<-1<<endl;
    }
  //  cout<<seg[1]<<endl;
    //for(int i=0;i<nn;i++)cout<<a[i]<<" ";cout<<endl;
}

int compare_plants(int x, int y){
	if(a[x]<a[y])return -1;
	else return 1;

}
/*
54321
00012
*/

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