Submission #1209427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209427		simona1230	Comparing Plants (IOI20_plants)	C++20	32 / 100	880 ms	45496 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int logg=20;
const int maxn=2*1e5+5;

struct node
{
    int vl,id,lz;
    node() {}
    node(int _vl,int _id,int _lz)
    {
        vl=_vl;
        id=_id;
        lz=_lz;
    }
};

node t[4*maxn];

node pull(node lf,node rt)
{
    node h=lf;
    if(lf.vl>rt.vl)h=rt;
    return h;
}

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

void updi(int i,int l,int r,int id,int vl)
{
    push(i,l,r);

    if(l==r)
    {
        t[i].vl=vl;
        t[i].id=l;
        return;
    }

    int m=(l+r)/2;
    push(i*2,l,m);
    push(i*2+1,m+1,r);
    if(id<=m)updi(i*2,l,m,id,vl);
    else updi(i*2+1,m+1,r,id,vl);

    t[i]=pull(t[i*2],t[i*2+1]);
}

void updr(int i,int l,int r,int ql,int qr)
{
    push(i,l,r);
    if(ql>qr)return;
    if(ql<=l&&r<=qr)
    {
        t[i].lz-=1;
        push(i,l,r);
        return;
    }

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

    t[i]=pull(t[i*2],t[i*2+1]);
}

node query(int i,int l,int r,int ql,int qr)
{
    push(i,l,r);
    if(ql>qr)return {maxn,0,0};
    if(ql<=l&&r<=qr)return t[i];
    int m=(l+r)/2;
    return pull(query(i*2,l,m,ql,min(qr,m)),query(i*2+1,m+1,r,max(m+1,ql),qr));
}

int g[maxn],op[maxn];
int sz,num;

int h[4*maxn];
void act(int i,int l,int r,int id,int vl)
{
    if(l==r)
    {
        h[i]=vl;
        return;
    }

    int m=(l+r)/2;
    if(id<=m)act(i*2,l,m,id,vl);
    else act(i*2+1,m+1,r,id,vl);

    h[i]=max(h[i*2],h[i*2+1]);
}

int qry(int i,int l,int r,int id)
{

    if(l>id)return 0;
    if(r<=id)
    {
        //cout<<l<<" "<<r<<" "<<id<<" "<<h[i]<<endl;
        return h[i];
    }
    int m=(l+r)/2;
    return max(qry(i*2,l,m,id),qry(i*2+1,m+1,r,id));
}

int lf[maxn][logg],rt[maxn][logg];
int kk;
void init(int k, std::vector<int> r)
{
    kk=k;
    num=r.size();
    sz=r.size();
    for(int i=0; i<r.size(); i++)
        updi(1,0,sz-1,i,r[i]);

    while(1)
    {
        stack<int> s;
        node x=query(1,0,sz-1,0,sz-1);

        if(x.vl!=0)break;

        s.push(x.id);
        while(s.size())
        {
            int y=s.top();
            node z=query(1,0,sz-1,max(0,y-k+1),y-1);
            if(y-k+1<0)z=pull(z,query(1,0,sz-1,sz+(y-k+1),sz-1));
            if(z.vl==0)s.push(z.id);
            else
            {
                op[num]=y;
                g[y]=num--;
                updr(1,0,sz-1,max(0,y-k+1),y-1);
                if(y-k+1<0)
                    updr(1,0,sz-1,sz+(y-k+1),sz-1);

                updi(1,0,sz-1,y,maxn);
                s.pop();
            }
        }
    }

    for(int i=sz-k+1;i<sz;i++)
    {
        //cout<<"++ "<<g[i]<<endl;
        act(1,1,sz,g[i],g[i]);
    }
    for(int i=0;i<sz;i++)
    {
        int x=i-k;
        if(x<0)x+=sz;
        act(1,1,sz,g[x],0);
        //cout<<"-- "<<g[x]<<endl;
        if(i)
        {
            //cout<<"++ "<<g[i-1]<<endl;
            act(1,1,sz,g[i-1],g[i-1]);
        }

        x=qry(1,1,sz,g[i]);
        if(x==0)x=-1;
        else x=op[x];

        lf[i][0]=x;
        //cout<<i<<" "<<x<<endl;
    }


    for(int i=0;i<sz;i++)
        act(1,1,sz,g[i],0);

    for(int i=1;i<k;i++)
    {
        //cout<<"++ "<<g[i]<<endl;
        act(1,1,sz,g[i],g[i]);
    }

    for(int i=0;i<sz;i++)
    {
        int x=i+k-1;
        if(x>=sz)x-=sz;
        act(1,1,sz,g[x],g[x]);
        act(1,1,sz,g[i],0);

        x=qry(1,1,sz,g[i]);
        if(x==0)x=-1;
        else x=op[x];

        rt[i][0]=x;
        //cout<<i<<" "<<x<<endl;
    }

    for(int j=1;j<logg;j++)
        for(int i=0;i<sz;i++)
        {
            if(lf[i][j-1]==-1)lf[i][j]=-1;
            else lf[i][j]=lf[lf[i][j-1]][j-1];
            if(rt[i][j-1]==-1)rt[i][j]=-1;
            else rt[i][j]=rt[rt[i][j-1]][j-1];
            //cout<<i<<" "<<j<<" "<<lf[i][j]<<" "<<rt[i][j]<<endl;
        }
    /*for(int i=0;i<r.size();i++)
        cout<<g[i]<<" ";
    cout<<endl;*/
}

int check(int x,int y)
{
    //cout<<x<<" >> "<<y<<endl;
    int z=x;
    for(int i=logg-1;i>=0;i--)
    {
        if(lf[z][i]!=-1&&g[lf[z][i]]>g[y]&&(x<y&&(lf[z][i]<x||lf[z][i]>=y)||x>y&&lf[z][i]>=y&&lf[z][i]<x))
            z=lf[z][i];
    }

    //cout<<"! "<<z<<endl;

    if(g[z]>=g[y]&&(z<=y&&sz-y+z<kk||z>=y&&z-y<kk))return 1;

    z=x;
    for(int i=logg-1;i>=0;i--)
    {
        if(rt[z][i]!=-1&&g[rt[z][i]]>g[y]&&(x<y&&rt[z][i]<=y&&rt[z][i]>x||x>y&&(rt[z][i]>x||rt[z][i]<=y)))
            z=rt[z][i];
    }

    //cout<<"!! "<<z<<endl;
    //cout<<"2- "<<z<<endl;

    if(g[z]>=g[y]&&(z<=y&&y-z<kk||z>=y&&sz-z+y<kk))return 1;

    return 0;
}

int compare_plants(int x, int y)
{
    int c1=check(x,y);
    int c2=check(y,x);
    //cout<<x<<" ? "<<y<<" "<<c1<<" "<<c2<<endl;
    if(c1&&!c2)return 1;
    if(!c1&&c2)return -1;
    return 0;
}

• Subtask 1: 5 / 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