Submission #1078849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078849		Faisal_Saqib	Comparing Plants (IOI20_plants)	C++17	5 / 100	103 ms	37720 KiB

plants

// #include "plants.h"
// #include <bits/stdc++.h>
// using namespace std;
// const int N=200100;
// int n,vis[N];
// vector<int> ma[N];
// void init(int k, std::vector<int> r) {
// 	n=r.size();
// 	for(int i=0;i<n;i++)
// 	{
// 		int j=(i+1)%n;
// 		if(r[i]==0)
// 		{
// 			// j < i
// 			ma[j].push_back(i);
// 		}
// 		else
// 		{
// 			// i < j
// 			ma[i].push_back(j);
// 		}
// 	}
// }
// void dfs(int x)
// {
// 	vis[x]=1;
// 	for(auto y:ma[x])
// 	{
// 		if(!vis[y])
// 		{
// 			dfs(y);
// 		}
// 	}
// }
// int compare_plants(int x, int y){
// 	for(int i=0;i<n;i++)vis[i]=0;
// 	dfs(x);
// 	if(vis[y])
// 	{
// 		return -1;
// 	}
// 	else
// 	{
// 		for(int i=0;i<n;i++)vis[i]=0;
// 		dfs(y);	
// 		if(vis[x])
// 		{
// 			return 1;
// 		}	
// 		else
// 		{
// 			return 0;
// 		}
// 	}
// 	// if(cp[x]==cp[y])
// 	// {
// 	// 	if(od[x]==od[y])return 0;
// 	// 	return ((od[x]<od[y])?-1:1);
// 	// }
// 	// else
// 	// 	return 0;
// }
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int N=200100;
const int LG=19;
int mi[N][LG],mx[N][LG],lg[N],n;
int get_mx(int l,int r)
{
	if(l>r)return -2;
	int lp=lg[r-l+1];
	//
	return max(mx[l][lp],mx[r-(1<<lp)+1][lp]);
}
int get_mi(int l,int r)
{
	if(l>r)return 2;
	int lp=lg[r-l+1];
	//
	return min(mi[l][lp],mi[r-(1<<lp)+1][lp]);
}
void init(int k, std::vector<int> r) {
	n=r.size();
	lg[0]=0;
	lg[1]=0;
	for(int i=2;i<=n;i++)
		lg[i]=lg[i/2]+1;
	for(int i=0;i<n;i++)
		mx[i][0]=mi[i][0]=r[i];
	for(int j=1;j<LG;j++)
	{
		for(int i=0;(i+(1<<j)-1)<n;i++)
		{
			mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
			mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
		}
	}
	return;
}
 
int compare_plants(int x, int y) {
	int mxp=get_mx(x,y-1);
	int mip=get_mi(x,y-1);
	if(mxp==mip)
	{
		if(mxp==0)
		{
			return 1;
		}
		else
		{
			return -1;
		}
	}
	else
	{
		int mx1=get_mx(y,n-1);
		int mi1=get_mi(y,n-1);
		mx1=max(mx1,get_mx(0,x-1));
		mi1=min(mi1,get_mi(0,x-1));
		if(mx1==mi1)
		{
			if(mx1==0)
			{
				return -1;
			}
			else 
			{
				return 1;
			}
		}
	}
	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