Submission #115406

#	Time	Username	Problem	Language	Result	Execution time	Memory
115406		davitmarg	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	92 ms	13516 KiB

railroad

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

struct yaxq
{
	int a, b, i;
	yaxq(int A=0,int B=0,int I=0)
	{
		a = A;
		b = B;
		i = I;
	}
};

bool operator<(yaxq p, yaxq q)
{
	if(p.a!=q.a)
		return p.a < q.a;
	return p.b < q.b;
}

int n,k;
pair<int, int> t[4 * 300005];
yaxq a[300005];
vector<yaxq> s,ans,ans2;
void build(int v, int l, int r)
{
	if (l == r)
	{
		t[v] = MP(s[l].b, l);
		return;
	}
	int m = (l + r) >> 1;
	build(v * 2, l, m);
	build(v * 2 + 1, m + 1, r);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

void update(int v,int l,int r,int pos,int val)
{
	if (l == r)
	{
		t[v].first = val;
		return;
	}
	int m = (l + r) >> 1;
	if (pos <= m)
		update(v * 2, l, m, pos, val);
	else
		update(v * 2 + 1, m + 1, r, pos, val);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

pair<int, int> get(int v,int l,int r,int i,int j)
{
	if (i > j)
		return MP(-mod, -1);
	if (l == i && r == j)
		return t[v];
	int m = (l + r) >> 1;
	return max(
		get(v * 2, l, m, i, min(j, m)),
		get(v * 2 + 1, m + 1, r, max(m + 1, i), j)
	);
}

int Main()
{
	for (int i = 1; i <= n; i++)
		s.PB(a[i]);

	ans.PB(yaxq(-mod, mod, 0));
	if (!s.empty())
	{
		sort(all(s));
		build(1, 0, s.size() - 1);
		while (1)
		{
			int l, r, m, pos = -1;
			l = 0;
			r = s.size() - 1;
			while (l <= r)
			{
				m = (l + r) >> 1;
				if (s[m].a < ans.back().b)
				{
					pos = m;
					l = m + 1;
				}
				else
					r = m - 1;
			}
			if (pos == -1)
				break;
			pair<int, int> nxt = get(1, 0, s.size() - 1, 0, pos);
			if (nxt.first == -mod)
				break;
			ans.PB(s[nxt.second]);
			update(1, 0, s.size() - 1, nxt.second, -mod);
		}

	}


	return 0;
}


LL plan_roller_coaster(vector<int> S, vector<int> T)
{
	n = S.size();
	for (int i = 1; i <= n; i++)
		a[i] = yaxq(S[i-1],T[i-1],i);
	Main();
	return !(ans.size()-1==s.size());
}

#ifdef death

int main()
{
	int N;
	vector<int> S, T;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		S.PB(0);
		cin >> S.back();
		T.PB(0);
		cin >> T.back();
	}
	cout << plan_roller_coaster(S, T) << endl;
	return 0;
}

#endif 


/*


*/

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