Submission #128213

#	Time	Username	Problem	Language	Result	Execution time	Memory
128213		ekrem	Roller Coaster Railroad (IOI16_railroad)	C++98	0 / 100	237 ms	24696 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;

typedef long long ll;
typedef pair < ll , ll > ii;
typedef vector < int > vi;

ll n, m, k, ans, top, ata[N];
pair < int , ii > a[N], b[N];

ll atabul(ll x){return ata[x] = (ata[x]==x)?x:atabul(ata[x]);}

ll plan_roller_coaster(vi x, vi y) {
	n = (int)x.size();
	for(int i = 0; i < n; i++){
		a[++m] = mp(x[i], mp(1, i));
		a[++m] = mp(y[i], mp(-1, i));
	}
	a[++m] = mp(inf, mp(1, n));
	a[++m] = mp(1, mp(-1, n));
	for(int i = 0; i <= n; i++)ata[i] = i;
	sort(a + 1, a + m + 1);
	for(int i = 1; i <= m; i++){
		top += a[i].nd.st;
		// cout << i << " " << a[i].st << " " << top << endl;
		ans += max(0ll, top)*(a[i + 1].st - a[i].st);
		b[++k] = mp(a[i + 1].st - a[i].st, mp(a[i + 1].nd.nd, a[i].nd.nd));
		if(top != 0){
			int xx = atabul(a[i + 1].nd.nd);
			int yy = atabul(a[i].nd.nd);
			if(xx != yy)
				ata[xx] = yy;
		}
	}
	sort(b + 1, b + k + 1);
	for(int i = 1; i <= k; i++){
		int xx = atabul(b[i].nd.st);
		int yy = atabul(b[i].nd.nd);
		if(xx != yy){
			ata[xx] = yy;
			ans += b[i].st;
		}
	}
	return ans;
}

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