Submission #1239643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239643		MuhammadSaram	Comparing Plants (IOI20_plants)	C++20	0 / 100	0 ms	328 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

const int M = 2e5 + 1;

pair<int,int> seg[M*2][2];
int lz[M*2][2], n, ty[M], ind[M], k;

void push(int v,int lc,int rc,int id)
{
	seg[lc][id].first+=lz[v][id], seg[rc][id].first+=lz[v][id];
	lz[lc][id]+=lz[v][id], lz[rc][id]+=lz[v][id];
	lz[v][id]=0;
}

pair<int,int> merge(pair<int,int> p,pair<int,int> p1)
{
	return (p.first<p1.first?p:p1);
}

void modify(int l,int r,int x,int id,int v=0,int s=0, int e=n)
{
	if (l>=e or r<=s) return;
	if (l<=s && e<=r)
	{
		seg[v][id].first+=x, lz[v][id]+=x;
		if (s+1==e) seg[v][id].second=s;
		return;
	}
	int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
	push(v,lc,rc,id);
	modify(l,r,x,id,lc,s,mid);
	modify(l,r,x,id,rc,mid,e);
	seg[v][id]=merge(seg[lc][id], seg[rc][id]);
}

void init(int K, vector<int> r)
{
	n=r.size(), k=K;
	for (int i=0;i<2*n;i++)
		seg[i][0]=seg[i][1]={M*2,-1};
	queue<pair<int,int>> q;
	for (int i=0;i<n;i++)
	{
		modify(i,i+1,r[i],1), modify(i,i+1,k-1-r[i],0);
		if (!r[i]) q.push({i,1});
		else if(k-1==r[i]) q.push({i,0});
		ind[i]=M*2;
	}
	int c=0;
	while (!q.empty())
	{
		pair<int,int> pp=q.front();q.pop();
		int i=pp.first, t=pp.second;
		ty[i]=t, ind[i]=c++;
		int l=(i-k+1+n)%n, r=(i+k)%n;
		if (l<r)
			modify(l,r,-1,1-t);
		else
			modify(0,r,-1,1-t), modify(l,n,-1,1-t);
		modify(i,i+1,M*3,0);
		modify(i,i+1,M*3,1);
		pair<int,int> p=seg[0][0], p1=seg[0][1];
		if (!p.first)
			q.push({p.second,0});
		if (!p1.first)
			q.push({p1.second,1});
	}
	return;
}

int compare_plants(int x, int y)
{
	bool b=(x+k-1>=y);
	bool b1=(y+k-1-n>=x);
	if (b)
	{
		if (ind[x]<M && (!b1 or ind[x]<ind[y]))
		{
			if (ty[x]) return -1;
			else return 1;
		}
	}
	if (b1)
	{
		if (ind[y]<M && (!b or ind[y]<ind[x]))
		{
			if (ty[y]) return 1;
			else return -1;
		}
	}
	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