oj.uz

Submission #1085794

# Submission time Handle Problem Language Result Execution time Memory
1085794 2024-09-08T17:39:00 Z TlenekWodoru Comparing Plants (IOI20_plants) C++17
44 / 100
 298 ms 30880 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19804 KB Output is correct
2 Correct 8 ms 19804 KB Output is correct
3 Correct 9 ms 20028 KB Output is correct
4 Incorrect 9 ms 19804 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19804 KB Output is correct
2 Correct 9 ms 19844 KB Output is correct
3 Correct 9 ms 19972 KB Output is correct
4 Correct 8 ms 20056 KB Output is correct
5 Correct 8 ms 20056 KB Output is correct
6 Correct 10 ms 20056 KB Output is correct
7 Correct 45 ms 24688 KB Output is correct
8 Correct 10 ms 20060 KB Output is correct
9 Correct 9 ms 20060 KB Output is correct
10 Correct 49 ms 24900 KB Output is correct
11 Correct 43 ms 24788 KB Output is correct
12 Correct 42 ms 24808 KB Output is correct
13 Correct 43 ms 24668 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19804 KB Output is correct
2 Correct 9 ms 19844 KB Output is correct
3 Correct 9 ms 19972 KB Output is correct
4 Correct 8 ms 20056 KB Output is correct
5 Correct 8 ms 20056 KB Output is correct
6 Correct 10 ms 20056 KB Output is correct
7 Correct 45 ms 24688 KB Output is correct
8 Correct 10 ms 20060 KB Output is correct
9 Correct 9 ms 20060 KB Output is correct
10 Correct 49 ms 24900 KB Output is correct
11 Correct 43 ms 24788 KB Output is correct
12 Correct 42 ms 24808 KB Output is correct
13 Correct 43 ms 24668 KB Output is correct
14 Correct 72 ms 25424 KB Output is correct
15 Correct 298 ms 30816 KB Output is correct
16 Correct 61 ms 25424 KB Output is correct
17 Correct 262 ms 30672 KB Output is correct
18 Correct 177 ms 30320 KB Output is correct
19 Correct 163 ms 30800 KB Output is correct
20 Correct 249 ms 30880 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19804 KB Output is correct
2 Correct 8 ms 19876 KB Output is correct
3 Correct 48 ms 24404 KB Output is correct
4 Correct 140 ms 29780 KB Output is correct
5 Correct 176 ms 30232 KB Output is correct
6 Correct 198 ms 30160 KB Output is correct
7 Correct 224 ms 30544 KB Output is correct
8 Correct 254 ms 30548 KB Output is correct
9 Correct 161 ms 29936 KB Output is correct
10 Correct 154 ms 29844 KB Output is correct
11 Correct 117 ms 29116 KB Output is correct
12 Correct 132 ms 29944 KB Output is correct
13 Correct 167 ms 30244 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19800 KB Output is correct
2 Correct 8 ms 19804 KB Output is correct
3 Incorrect 7 ms 19804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19960 KB Output is correct
2 Correct 7 ms 19804 KB Output is correct
3 Incorrect 8 ms 19844 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19804 KB Output is correct
2 Correct 8 ms 19804 KB Output is correct
3 Correct 9 ms 20028 KB Output is correct
4 Incorrect 9 ms 19804 KB Output isn't correct
5 Halted 0 ms 0 KB -