제출 #128215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128215		ekrem	Roller Coaster Railroad (IOI16_railroad)	C++98	100 / 100	1682 ms	73432 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])*qu(i);
    		} 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: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36