Submission #1224768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224768		PVM_pvm	Comparing Plants (IOI20_plants)	C++20	5 / 100	123 ms	13296 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200'007
int prm[MAXN];
vector<int> rr;
int N;
long long segg[4*MAXN],segm[4*MAXN];
void Initialise(int ind, int l, int r)
{
    if (l==r)
    {
        segg[ind]=rr[l];
        segm[ind]=rr[l];
        return;
    }
    int mid=(l+r)/2;
    Initialise(ind*2,l,mid);
    Initialise(ind*2+1,mid+1,r);
    segg[ind]=max(segg[ind*2],segg[ind*2+1]);
    segm[ind]=min(segm[ind*2],segm[ind*2+1]);
    //if (l==2 && r==3) cout<<segg[ind]<<" "<<segg[ind*2]<<" "<<segg[ind*2+1]<<"aa\n";
}
long long qm,qg;
void Query(int ind, int l, int r, int ql, int qr)
{
    if (ql<=l && qr>=r)
    {
        //cout<<ind<<" "<<l<<" "<<r<<" "<<segm[ind]<<" "<<segg[ind]<<"\n";
        qm=min(qm,segm[ind]);
        qg=max(qg,segg[ind]);
        return;
    }
    int mid=(l+r)/2;
    if (ql<=mid) Query(ind*2,l,mid,ql,qr);
    if (qr>=mid+1) Query(ind*2+1,mid+1,r,ql,qr);
}
void init(int k, vector<int> r) {
    int n=r.size();
    rr=r;
    N=n;
    Initialise(1,0,n-1);
    //for (int q=0;q<n;q++) cout<<prm[q]<<" ";
	return;
}

int compare_plants(int x, int y) {
	int obr=1;
	if (x>y)
    {
        swap(x,y);
        obr=-1;
    }
	qm=3;
	qg=-1;
	Query(1,0,N-1,x,y-1);
    //cout<<qm<<" "<<qg<<"\n";
    if (qm==qg)
    {
        if (qm==0)
        {
            ///x e poveche ot y
            return obr;
        }
        if (qm==1)
        {
            ///x e pomalko ot y
            return -1*obr;
        }
    }
    qm=3;
    qg=-1;
    Query(1,0,N-1,y,N-1);
    if (x!=0) Query(1,0,N-1,0,x-1);
    //cout<<qm<<" "<<qg<<"\n\n";
    if (qm==qg)
    {
        if (qm==0)
        {
            ///y e poveche ot x
            return -1*obr;
        }
        if (qm==1)
        {
            return obr;
        }
    }
	return 0;
}

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