Submission #1085794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085794		TlenekWodoru	Comparing Plants (IOI20_plants)	C++17	44 / 100	298 ms	30880 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];
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);
    }
	return;
}
int compare_plants(int x, int y)
{
    if(examp[x]>examp[y]){return 1;}
    else{return -1;}
}

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25