Submission #373038

#	Time	Username	Problem	Language	Result	Execution time	Memory
373038		Jasiekstrz	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	310 ms	14592 KiB

railroad

#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
struct Road
{
	int s,t;
	inline bool operator<(const Road &oth)
	{
		if(t==oth.t)
			return s<oth.s;
		return t<oth.t;
	}
};
struct Small
{
	int t,id;
	inline bool operator<(const Small &oth) const
	{
		if(t==oth.t)
			return id<oth.id;
		return t<oth.t;
	}
};
struct Big
{
	int s,id;
	inline bool operator<(const Big &oth) const
	{
		if(s==oth.s)
			return id<oth.id;
		return s<oth.s;
	}
};
const int N=2e5;
const int INF=1e9+7;
Road tab[N+10];
set<Small> sm;
set<Big> bg;
long long plan_roller_coaster(vector<int> s,vector<int> t)
{
	int n=s.size();
	for(int i=0;i<n;i++)
		tab[i]={s[i],t[i]};
	sort(tab,tab+n);
	sm.insert({0,n});
	bg.insert({INF,n});
	for(int i=0;i<n;i++)
	{
		while(!bg.empty() && (bg.begin()->s)<tab[i].t)
		{
			auto x=*bg.begin();
			bg.erase(x);
			auto it=prev(sm.end());
			if((it->id)==x.id)
				it--;
			sm.erase(it);
		}
		auto it=sm.upper_bound({tab[i].s,INF});
		if(it==sm.begin() || sm.empty())
		{
			return 1;
		}
		if(tab[i].s>tab[i].t)
		{
			sm.insert({tab[i].t,i});
			bg.insert({tab[i].s,i});
		}
		else
		{
			sm.erase(prev(it));
			sm.insert({tab[i].t,i});
		}
	}
	return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36