Submission #134637

#	Time	Username	Problem	Language	Result	Execution time	Memory
134637		Mahdi_Jfri	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	231 ms	10208 KiB

railroad

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

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 2e5 + 20;

int s[maxn] , t[maxn] , n , ind[maxn];

pair<int , int> mn[maxn * 4];

bool cmps(int a , int b)
{
	return s[a] < s[b];
}

void build(int s = 0 , int e = n , int v = 1)
{
	if(e - s < 2)
	{
		mn[v] = {t[s] , s};
		return;
	}

	int m = (s + e) / 2;
	build(s , m , 2 * v);
	build(m , e , 2 * v + 1);

	mn[v] = min(mn[2 * v] , mn[2 * v + 1]);
}

void rem(int p , int s = 0 , int e = n , int v = 1)
{
	if(e - s < 2)
	{
		mn[v] = {2e9 , -1};
		return;
	}

	int m = (s + e) / 2;
	if(p < m)
		rem(p , s , m , 2 * v);
	else
		rem(p , m , e , 2 * v + 1);

	mn[v] = min(mn[2 * v] , mn[2 * v + 1]);
}

pair<int , int> get(int l , int r , int s = 0 , int e = n , int v = 1)
{
	if(l <= s && e <= r)
		return mn[v];
	if(r <= s || e <= l)
		return make_pair(2e9 , -1);

	int m = (s + e) / 2;
	return min(get(l , r , s , m , 2 * v) , get(l , r , m , e , 2 * v + 1));
}

long long plan_roller_coaster(vector<int> S, vector<int> T)
{
    n = (int)S.size();
	for(int i = 0; i < n; i++)
		s[i] = S[i] , t[i] = T[i] , ind[i] = i;

	sort(ind , ind + n , cmps);
	for(int i = 0; i < n; i++)
		s[i] = S[ind[i]] , t[i] = T[ind[i]];

	build();

	int val = 1;
	for(int _ = 0; _ < n; _++)
	{
		int k = lower_bound(s , s + n , val) - s;
		auto tmp = get(k , n);
		k = tmp.second , val = tmp.first;
		if(k < 0)
			return 1;

		rem(k);
	}

	return 0;
}

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