Submission #1208179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208179		simona1230	Comparing Plants (IOI20_plants)	C++20	0 / 100	4096 ms	320 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)
{
    k--;

    /*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]--;
                }
                g[c[i]]=r.size()-num;
            }
            for(int i=0;i<r.size();i++)
                cout<<g[i]<<" ";
            cout<<endl;
            num++;
            taken+=c.size();
        }

        return;
    }*/
    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];

    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;
        while(1)
        {
            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 0;
    if(g[x]>g[y])return 1;
    return -1;
}

• 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