Submission #1085805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085805		TlenekWodoru	Comparing Plants (IOI20_plants)	C++17	0 / 100	11 ms	20032 KiB

plants

#include<bits/stdc++.h>
#include "plants.h"
using namespace std;
const int INF=1e8+9;
struct Node
{
    int minn;
    int lewy,prawy;
    int MaxxDiff,ind;
    Node(int minn=0, int lewy=0, int prawy=0, int MaxxDiff=0, int ind=0) : minn(minn),lewy(lewy),prawy(prawy),MaxxDiff(MaxxDiff),ind(ind){}
    Node operator*(const Node &B)const
    {
        if(minn<B.minn)
        {
            return {minn,lewy,prawy,MaxxDiff,ind};
        }
        else if(B.minn<minn){return B;}
        else
        {
            int Mu=MaxxDiff,u=ind;
            if(B.MaxxDiff>Mu)
            {
                Mu=B.MaxxDiff;
                u=B.ind;
            }
            int kand=B.lewy-prawy;
            if(kand>Mu)
            {
                Mu=kand;
                u=B.lewy;
            }
            return {minn,min(lewy,B.lewy),max(prawy,B.prawy),Mu,u};
        }
    }
    Node& operator +=(const int &dod)
    {
        this->minn+=dod;
        return *this;
    }
};
vector<int>tab;
vector<int>examp;
int Gwiazdka[1000000];
Node Tre[1000000];
int n,k,base;
pair<int,int>Tre2[1000000];
int JumpL[400009][20],JumpP[400009][20];
void Przedzial(int v, int a, int b, const int &l, const int &p, const int &dod)
{
    if(b<l||p<a){return;}
    if(l<=a&&b<=p)
    {
        Gwiazdka[v]+=dod;
        Tre[v]+=dod;
    }
    else
    {
        const int mid=(a+b)>>1;
        if(Gwiazdka[v]!=0)
        {
            Gwiazdka[v*2]+=Gwiazdka[v];
            Gwiazdka[v*2+1]+=Gwiazdka[v];
            Tre[v*2]+=Gwiazdka[v];
            Tre[v*2+1]+=Gwiazdka[v];
            Gwiazdka[v]=0;
        }
        Przedzial(v*2,a,mid,l,p,dod);
        Przedzial(v*2+1,mid+1,b,l,p,dod);
        Tre[v]=Tre[v*2]*Tre[v*2+1];
    }
}
int TworzenieDrzewa(int x)
{
    int u=1;
    while(x>0)
    {
        x>>=1;
        u<<=1;
    }
    return u;
}
int GetZiom()
{
    Node xd=Tre[1];
    if(xd.lewy==xd.prawy){return xd.lewy;}
    int kand=xd.lewy+n-xd.prawy;
    if(kand>xd.MaxxDiff)
    {
        return xd.lewy;
    }
    else
    {
        return xd.ind;
    }
}
void init(int K, vector<int>TAB)
{
    K--;
    tab=TAB;
    n=(int)tab.size();
    examp.resize(n);
    k=K;
    base=TworzenieDrzewa(n);
    for(int i=0;i<n;i++)
    {
        Tre[i+base].minn=tab[i];
    }
    for(int i=n;i<base;i++)
    {
        Tre[i+base].minn=INF;
    }
    for(int i=0;i<base;i++)
    {
        Tre[i+base].lewy=i;
        Tre[i+base].prawy=i;
        Tre[i+base].MaxxDiff=-1;
        Tre[i+base].ind=-1;
    }
    for(int i=base-1;i>0;i--)
    {
        Tre[i]=Tre[i*2]*Tre[i*2+1];
    }
    for(int i=1;i<=n;i++)
    {
        int u=GetZiom();
        examp[u]=n-i+1;
        int l=(n+u-k)%n;
        int p=(n+u-1)%n;
        if(l<=p)
        {
            Przedzial(1,0,base-1,l,p,-1);
        }
        else
        {
            Przedzial(1,0,base-1,l,n-1,-1);
            Przedzial(1,0,base-1,0,p,-1);
        }
        Przedzial(1,0,base-1,u,u,INF);
    }
    for(int i=0;i<n;i++)
    {
        examp.push_back(examp[i]);
    }
    set<pair<int,int>>S={{-1,-1}};
    for(int i=0;i<n*2;i++)
    {
        pair<int,int>xd=*next(S.lower_bound({examp[i],i}),-1);
        JumpL[i][0]=xd.second;
        S.insert({examp[i],i});
        if(i-k>=0)
        {
            S.erase({examp[i-k],i-k});
        }
    }
    for(int i=n*2-1;i>=0;i--)
    {
        pair<int,int>xd=*next(S.lower_bound({examp[i],i}),-1);
        JumpP[i][0]=xd.second;
        S.insert({examp[i],i});
        if(i+k<n*2)
        {
            S.erase({examp[i+k],i+k});
        }
    }
    for(int i=0;i<n*2;i++)
    {
        for(int j=1;j<20;j++)
        {
            if(JumpL[i][j-1]==-1){JumpL[i][j]=-1;}
            else{JumpL[i][j]=JumpL[i][JumpL[i][j-1]];}
        }
    }
    for(int i=n*2-1;i>=0;i--)
    {
        for(int j=1;j<20;j++)
        {
            if(JumpP[i][j-1]==-1){JumpP[i][j]=-1;}
            else{JumpP[i][j]=JumpP[i][JumpP[i][j-1]];}
        }
    }
	return;
}
int compare_plants(int x, int y)
{
    if(x==y){return 0;}
    int mnoznik=1;
    if(examp[x]<examp[y])
    {
        mnoznik=-1;
        swap(x,y);
    }
    ///Czy H[x] > H[y];
    int a,b;
    a=x;
    b=y;
    if(b<a){b+=n;}
    for(int i=19;i>=0;i--)
    {
        if(JumpP[a][i]!=-1&&JumpP[a][i]<b)
        {
            a=JumpP[a][i];
        }
    }
    if(b-a<=k&&examp[a]>examp[b]){return mnoznik;}
    a=x;
    b=y;
    if(a<b){a+=n;}
    for(int i=19;i>=0;i--)
    {
        if(JumpL[a][i]!=-1&&b<JumpL[a][i])
        {
            a=JumpL[a][i];
        }
    }
    if(a-b<=k&&examp[a]>examp[b]){return mnoznik;}
    return 0;
}

• 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