제출 #128183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128183		ekrem	Roller Coaster Railroad (IOI16_railroad)	C++98	30 / 100	1449 ms	69724 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, ans, fen[N], ne[N], ata[N];
map < ll , ll > h, hh;
map < ll , ll > :: iterator it;
ii a[N];

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

void upp(ll x, ll y){
	for(; x < N; x += x&-x)
		fen[x] += y;
}

void up(ll x, ll y, ll z){
	upp(x, z);
	upp(y + 1, -z);
}

ll qu(ll x){
	ll ans = 0;
	for(; x > 0; x -= x&-x)
		ans += fen[x];
	return ans;
}

ll plan_roller_coaster(vi x, vi y) {
	x.pb(inf);y.pb(-inf);
	n = (int)x.size();x.insert(x.begin(), 0);y.insert(y.begin(), 0);
	hh[inf]++;
	h[-inf]++;
	for(ll i = 1; i <= n; i++){
		hh[x[i]]++;
		hh[y[i]]++;
	}
	for(it = hh.begin(); it != hh.end(); it++){
		h[it->st] = ++m;
		ne[m] = it->st;
		ata[m] = m;
	}
	for(ll i = 1; i <= n; i++){
		// cout << h[x[i]] << " " << h[y[i]] << endl;
		ll xx = atabul(h[x[i]]);
		ll yy = atabul(h[y[i]]);
		if(xx != yy)
			ata[xx] = yy;
		if(x[i] < y[i])
			up(h[x[i]] + 1, h[y[i]], 1);
		else if(y[i] < x[i])
			up(h[y[i]] + 1, h[x[i]], -1);
	}
	for(ll i = 1; i <= m; i++){
		if(qu(i) > 0){
			// cout << i << " " << qu(i) << endl;
			ll xx = atabul(i);
			ll yy = atabul(i - 1);
			if(xx != yy)
				ata[xx] = yy;
			ans += ne[i] - ne[i - 1];
		} else if(qu(i) < 0){
			ll xx = atabul(i);
			ll yy = atabul(i - 1);
			if(xx != yy)
				ata[xx] = yy;
		}
		if(i >= 2)
			a[i] = mp(ne[i] - ne[i - 1], i);
		// cout << "ve " << ne[i] << " " << qu(i) - 1 << endl;
	}
	sort(a + 2, a + m + 1);
	for(ll i = 2; i <= m; i++){
		ll j = a[i].nd;
		ll xx = atabul(j);
		ll yy = atabul(j - 1);
		if(xx != yy){
			ata[xx] = yy;
			if(j != m)
				ans += ne[j] - ne[j - 1];
			// cout << ne[j] - ne[j - 1] << " eklendi" << endl;
		}
	}
	return ans;
}

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