Submission #1194979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194979		simona1230	식물 비교 (IOI20_plants)	C++20	In queue	0 ms	0 KiB

plants

#include "plants.h"

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=2*1e5+5;
int nn;
int lz[4*maxn];
int vl[4*maxn];
int id[4*maxn];
int a[maxn];
void pull(int i)
{
    vl[i]=min(vl[i*2],vl[i*2+1]);
    if(vl[i*2]<=vl[i*2+1])id[i]=id[i*2];
    else id[i]=id[i*2+1];
}

void build(int i,int l,int r)
{
    if(l==r)
    {
        vl[i]=a[l];
        id[i]=l;
        return;
    }

    int m=(l+r)/2;
    build(i*2,l,m);
    build(i*2+1,m+1,r);

    pull(i);
    //cout<<l<<" "<<r<<" "<<vl[i]<<" "<<id[i]<<endl;
}

void push(int i,int l,int r)
{
    vl[i]-=lz[i];
    if(l!=r)
    {
        lz[i*2]+=lz[i];
        lz[i*2+1]+=lz[i];
    }
    lz[i]=0;
}

void update(int i,int l,int r,int ql,int qr)
{
    push(i,l,r);
    if(ql>qr)return;
    if(ql<=l&&r<=qr)
    {
        lz[i]+=1;
        push(i,l,r);
        //cout<<"> "<<l<<" "<<r<<" "<<vl[i]<<" "<<id[i]<<endl;
        return;
    }

    int m=(l+r)/2;
    update(i*2,l,m,ql,min(qr,m));
    update(i*2+1,m+1,r,max(m+1,ql),qr);

    pull(i);
    //cout<<"> "<<l<<" "<<r<<" "<<vl[i]<<" "<<id[i]<<endl;
}

pair<int,int> query(int i,int l,int r,int ql,int qr)
{
    push(i,l,r);
    if(ql>qr)return {1e9,1e9};
    if(ql<=l&&r<=qr)return {vl[i],id[i]};
    int m=(l+r)/2;
    pair<int,int> q1=query(i*2,l,m,ql,min(qr,m));
    pair<int,int> q2=query(i*2+1,m+1,r,max(m+1,ql),qr);

    if(q1.first<=q2.first)return q1;
    return q2;
}

void use(int i,int l,int r,int idx)
{
    push(i,l,r);
    if(idx>r||idx<l)return;
    if(l==r)
    {
        vl[i]=1e9;
        id[i]=l;
        return;
    }

    int m=(l+r)/2;
    use(i*2,l,m,idx);
    use(i*2+1,m+1,r,idx);

    pull(i);
}
int g[maxn];

void init(int k, std::vector<int> r)
{
    for(int i=0;i<r.size();i++)
        g[i]=0;
    nn=r.size();
    for(int i=0;i<r.size();i++)
        a[i]=r[i];

    for(int i=0;i<r.size();i++)
    {
        vector<int> h;
        for(int j=0;j<r.size();j++)
        {
            if(g[j])continue;
            if(a[j]==0)h.push_back(j);
        }

        if(h.size()==0)
        {
            cout<<"on"<<endl;
            break;
        }

        int curr=h[0];
        for(int j=1;j<h.size();j++)
        {
            if(h[j]-h[j-1]>k)
            {
                curr=h[j];
            }
        }

        g[curr]=nn-i;

        for(int j=1;j<=k;j++)
        {
            curr--;
            if(curr==-1)curr=nn-1;
            a[curr]--;
        }
    }
    /*build(1,0,nn-1);
    //cout<<"here"<<endl;
    for(int i=0;i<r.size();i++)
    {
        //cout<<i<<"! "<<endl;
        pair<int,int> p=query(1,0,nn-1,0,nn-1);
        //cout<<p.first<<" "<<p.second<<endl;
        if(p.second<k)
        {
            int lf=nn-(k-p.second);
            pair<int,int> p1=query(1,0,nn-1,lf,nn-1);
            if(p1.first==p.first)p=p1;
        }


        use(1,0,nn-1,p.second);
        g[p.second]=nn-i;
        update(1,0,nn-1,max(0,p.second-k),p.second-1);
        //cout<<"- "<<max(0,p.second-k)<<" "<<p.second-1<<endl;
        if(p.second<k)
        {
            int lf=nn-(k-p.second);
            update(1,0,nn-1,lf,nn-1);
            //cout<<"- "<<lf<<" "<<nn-1<<endl;
        }
    }*/

    /*for(int i=0;i<nn;i++)
        cout<<g[i]<<" ";
    cout<<endl;*/
}

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