Submission #1208185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208185		simona1230	식물 비교 (IOI20_plants)	C++20	27 / 100	290 ms	16160 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],g1[maxn];

void init(int k, std::vector<int> r)
{
    k--;

    vector<int> rr=r;
    if(r.size()<=100)
    {
        int taken=0,num=0;
        while(taken!=r.size())
        {
            vector<int> z;
            for(int i=0;i<r.size();i++)
                if(r[i]==0)z.push_back(i);
            vector<int> c;
            for(int i=0;i<z.size();i++)
                if(i==0&&(r.size()-z[z.size()-1]+z[i])>k||i!=0&&z[i]-z[i-1]>k)
                    c.push_back(z[i]);

            for(int i=0;i<c.size();i++)
            {
                int j=c[i];
                r[j]--;
                for(int l=1;l<=k;l++)
                {
                    j--;
                    if(j==-1)j=r.size()-1;
                    r[j]--;
                }
                g1[c[i]]=r.size()-num;
            }
        /*for(int i=0;i<r.size();i++)
            cout<<g1[i]<<" ";
        cout<<endl;*/
            num++;
            taken+=c.size();
        }

        return;
    }
    memset(lz,0,sizeof(lz));
    memset(vl,0,sizeof(vl));
    memset(id,0,sizeof(id));

    r=rr; /*cout<<k<<endl;
    for(int i=0;i<r.size();i++)
        cout<<r[i]<<" ";
    cout<<endl;*/
    for(int i=0;i<r.size();i++)
        g1[i]=0;
    nn=r.size();
    for(int i=0;i<r.size();i++)
        a[i]=r[i];

    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);
        g1[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++)
    {
        if(g1[i]!=g[i])
        {
            cout<<k<<" "<<r.size()<<endl;
            for(int j=0;j<r.size();j++)
                cout<<g[j]<<" ";
            cout<<endl;
            exit(0);
        }
    }
    cout<<"out"<<endl;*/
    /*for(int i=0;i<nn;i++)
        cout<<g[i]<<" ";
    cout<<endl;*/
}

int compare_plants(int x, int y)
{
    if(g1[x]==g1[y])return 0;
    if(g1[x]>g1[y])return 1;
    return -1;
}
/*
int main()
{
    while(1)
    {
        int n,k;
        n=5;
        k=3;
        for(int i=0;i<n;i++)
            a[i]=i+1;
        random_shuffle(a,a+n);
        vector<int> r;
        for(int i=0;i<n;i++)
        {
            int x=i;
            int cnt=0;
            for(int j=1;j<k;j++)
            {
                x++;
                if(x==n)x=0;
                if(a[x]>a[i])cnt++;
            }
            r.push_back(cnt);
        }

        init(k,r);
    }
}*/

• 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