Submission #1255273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255273		Joon_Yorigami	Comparing Plants (IOI20_plants)	C++20	49 / 100	394 ms	19144 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vint = vector<int>;
constexpr int maxn = 200'000;
bool k2check=false;
ll pref[maxn+5];
ll n;
ll k;
ll segmin[4*maxn];
ll segidx[4*maxn];
ll seglazy[4*maxn];
ll ans[maxn];
vint r;

void range_update(int id, int l, int r, int ql, int qr, ll delta) {
    if(qr<=l||r<=ql)
		return;
    if(ql<=l&&r<=qr)
	{
        segmin[id]+=delta;
        seglazy[id]+=delta;
        return;
    }
    int lc=id*2,rc=id*2+1;
    if(seglazy[id]!=0)
	{
        segmin[lc]  += seglazy[id];
        seglazy[lc] += seglazy[id];
        segmin[rc]  += seglazy[id];
        seglazy[rc] += seglazy[id];
        seglazy[id] = 0;
    }
    int m=l+(r-l)/2;
    range_update(lc,l,m,ql,qr,delta);
    range_update(rc,m,r,ql,qr,delta);
    if(segmin[lc]<=segmin[rc])
	{
        segmin[id]=segmin[lc];
        segidx[id]=segidx[lc];
    }
	else
	{
        segmin[id]=segmin[rc];
        segidx[id]=segidx[rc];
    }
}

pair<ll,int> range_query(int id, int l, int r, int ql, int qr)
{
	//val idx
    if(qr<=l||r<=ql)
        return {LONG_LONG_MAX,-1};
    if(ql<=l&&r<=qr)
        return {segmin[id],segidx[id]};
    int lc=id*2,rc=id*2+1;
    if(seglazy[id]!=0)
	{
        segmin[lc]+=seglazy[id];
        seglazy[lc]+=seglazy[id];
        segmin[rc]+=seglazy[id];
        seglazy[rc]+=seglazy[id];
        seglazy[id]=0;
    }
    int m=l+(r-l)/2;
    pair<ll,int> left=range_query(lc,l,m,ql,qr);
    pair<ll,int> right=range_query(rc,m,r,ql,qr);
    return (left.first<=right.first?left:right);
}

void init(int K, std::vector<int> R) {
	k2check=false;
	r=R;
	k=K;
	if(K==2)
		k2check=true;
	n=r.size();
	if(k==2)
	{
		pref[0]=0;
		for(int i=0;i<n;i++)
		{
			pref[i+1]=pref[i]+r[i];
		}
		return;
	}
	ll segsize=1;
	while(segsize<n)
		segsize<<=1;
	for(int i=0;i<segsize*2;i++)
	{
		segmin[i]=LONG_LONG_MAX;
		seglazy[i]=0;
		segidx[i]=-1;
	}
	for(ll i=0;i<n;i++)
    {
      	segmin[segsize+i]=r[i];
	  	seglazy[segsize+i]=0;
	  	segidx[segsize+i]=i;
    }
    for(ll i=segsize-1;i>0;i--)
    {
		seglazy[i]=0;
      	segmin[i]=min(segmin[i*2],segmin[i*2+1]);
		if(segmin[i*2]<=segmin[i*2+1])
			segidx[i]=segidx[i*2];
		else
			segidx[i]=segidx[i*2+1];
    }
	int x = n;
	ll minval,minid;
	while(true)
	{
		stack<ll> stk;
		pair<ll,int> ret;
		ret=range_query(1, 0, segsize, 0, n);
		minval=ret.first;
		minid=ret.second;
        if(minval!=0)
			break;
		stk.push(minid);
		while(!stk.empty())
		{
			ll curr=stk.top();
			int l=curr-k+1,r=curr;
			pair<ll,int> cand={LONG_LONG_MAX,-1};
			if(l<0)
				cand=(range_query(1,0,segsize,0,r).first<=range_query(1,0,segsize,n+l,n).first ? range_query(1,0,segsize,0,r) : range_query(1,0,segsize,n+l,n));
			else
				cand=range_query(1,0,segsize,l,r);
			if(cand.first==0)
				stk.push(cand.second);
			else
			{
				ans[curr]=--x;
				if(l<0)
				{
					range_update(1,0,segsize,0,r,-1);
					range_update(1,0,segsize,n+l,n,-1);
				}
				else
					range_update(1,0,segsize,l,r,-1);
				range_update(1,0,segsize,curr,curr+1,LONG_LONG_MAX>>1);
				stk.pop();
			}
		}
	}
	return;
}

int compare_plants(int x, int y) {
	if(k2check)
	{
		if(pref[y]-pref[x]==0 || pref[n]-pref[y]+pref[x]==n-y+x)
			return 1;
		else if(pref[y]-pref[x]==y-x || pref[n]-pref[y]+pref[x]==0)
			return -1;
		else
			return 0;
	}
	return (ans[x]<ans[y] ? -1 : 1);
}

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