oj.uz

Submission #128215

# Submission time Handle Problem Language Result Execution time Memory
128215 2019-07-10T14:20:50 Z ekrem Roller Coaster Railroad (IOI16_railroad) C++
100 / 100
 1682 ms 73432 KB 
    #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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 2
2 Correct 2 ms 376 KB n = 2
3 Correct 3 ms 380 KB n = 2
4 Correct 2 ms 376 KB n = 2
5 Correct 3 ms 376 KB n = 2
6 Correct 3 ms 376 KB n = 2
7 Correct 2 ms 376 KB n = 3
8 Correct 2 ms 380 KB n = 3
9 Correct 2 ms 376 KB n = 3
10 Correct 2 ms 376 KB n = 8
11 Correct 2 ms 376 KB n = 8
12 Correct 2 ms 376 KB n = 8
13 Correct 2 ms 376 KB n = 8
14 Correct 2 ms 376 KB n = 8
15 Correct 2 ms 376 KB n = 8
16 Correct 2 ms 412 KB n = 8
17 Correct 2 ms 376 KB n = 8
18 Correct 2 ms 380 KB n = 8
19 Correct 2 ms 376 KB n = 3
20 Correct 1 ms 376 KB n = 7
21 Correct 2 ms 376 KB n = 8
22 Correct 3 ms 376 KB n = 8
23 Correct 2 ms 376 KB n = 8
24 Correct 2 ms 376 KB n = 8
25 Correct 2 ms 376 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 2
2 Correct 2 ms 376 KB n = 2
3 Correct 3 ms 380 KB n = 2
4 Correct 2 ms 376 KB n = 2
5 Correct 3 ms 376 KB n = 2
6 Correct 3 ms 376 KB n = 2
7 Correct 2 ms 376 KB n = 3
8 Correct 2 ms 380 KB n = 3
9 Correct 2 ms 376 KB n = 3
10 Correct 2 ms 376 KB n = 8
11 Correct 2 ms 376 KB n = 8
12 Correct 2 ms 376 KB n = 8
13 Correct 2 ms 376 KB n = 8
14 Correct 2 ms 376 KB n = 8
15 Correct 2 ms 376 KB n = 8
16 Correct 2 ms 412 KB n = 8
17 Correct 2 ms 376 KB n = 8
18 Correct 2 ms 380 KB n = 8
19 Correct 2 ms 376 KB n = 3
20 Correct 1 ms 376 KB n = 7
21 Correct 2 ms 376 KB n = 8
22 Correct 3 ms 376 KB n = 8
23 Correct 2 ms 376 KB n = 8
24 Correct 2 ms 376 KB n = 8
25 Correct 2 ms 376 KB n = 8
26 Correct 2 ms 376 KB n = 8
27 Correct 2 ms 376 KB n = 8
28 Correct 2 ms 348 KB n = 8
29 Correct 2 ms 376 KB n = 16
30 Correct 2 ms 376 KB n = 16
31 Correct 2 ms 376 KB n = 16
32 Correct 2 ms 376 KB n = 16
33 Correct 2 ms 376 KB n = 16
34 Correct 2 ms 376 KB n = 16
35 Correct 2 ms 376 KB n = 16
36 Correct 2 ms 376 KB n = 15
37 Correct 2 ms 376 KB n = 8
38 Correct 2 ms 352 KB n = 16
39 Correct 3 ms 376 KB n = 16
40 Correct 2 ms 376 KB n = 9
41 Correct 2 ms 376 KB n = 16
42 Correct 2 ms 376 KB n = 16
43 Correct 2 ms 376 KB n = 16
44 Correct 3 ms 376 KB n = 9
45 Correct 2 ms 376 KB n = 15
46 Correct 2 ms 376 KB n = 16
47 Correct 2 ms 376 KB n = 16
48 Correct 2 ms 376 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1368 ms 69224 KB n = 199999
2 Correct 1410 ms 69344 KB n = 199991
3 Correct 1377 ms 69244 KB n = 199993
4 Correct 996 ms 52904 KB n = 152076
5 Correct 546 ms 32512 KB n = 93249
6 Correct 1138 ms 57304 KB n = 199910
7 Correct 1176 ms 67936 KB n = 199999
8 Correct 1052 ms 57816 KB n = 199997
9 Correct 1150 ms 59448 KB n = 171294
10 Correct 917 ms 48936 KB n = 140872
11 Correct 1142 ms 58456 KB n = 199886
12 Correct 1208 ms 68356 KB n = 199996
13 Correct 1057 ms 60376 KB n = 200000
14 Correct 1071 ms 68312 KB n = 199998
15 Correct 1078 ms 67652 KB n = 200000
16 Correct 1212 ms 69780 KB n = 199998
17 Correct 1675 ms 69832 KB n = 200000
18 Correct 1682 ms 66300 KB n = 190000
19 Correct 1264 ms 62216 KB n = 177777
20 Correct 526 ms 35392 KB n = 100000
21 Correct 1234 ms 69852 KB n = 200000
22 Correct 1332 ms 69712 KB n = 200000
23 Correct 1373 ms 69864 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 2
2 Correct 2 ms 376 KB n = 2
3 Correct 3 ms 380 KB n = 2
4 Correct 2 ms 376 KB n = 2
5 Correct 3 ms 376 KB n = 2
6 Correct 3 ms 376 KB n = 2
7 Correct 2 ms 376 KB n = 3
8 Correct 2 ms 380 KB n = 3
9 Correct 2 ms 376 KB n = 3
10 Correct 2 ms 376 KB n = 8
11 Correct 2 ms 376 KB n = 8
12 Correct 2 ms 376 KB n = 8
13 Correct 2 ms 376 KB n = 8
14 Correct 2 ms 376 KB n = 8
15 Correct 2 ms 376 KB n = 8
16 Correct 2 ms 412 KB n = 8
17 Correct 2 ms 376 KB n = 8
18 Correct 2 ms 380 KB n = 8
19 Correct 2 ms 376 KB n = 3
20 Correct 1 ms 376 KB n = 7
21 Correct 2 ms 376 KB n = 8
22 Correct 3 ms 376 KB n = 8
23 Correct 2 ms 376 KB n = 8
24 Correct 2 ms 376 KB n = 8
25 Correct 2 ms 376 KB n = 8
26 Correct 2 ms 376 KB n = 8
27 Correct 2 ms 376 KB n = 8
28 Correct 2 ms 348 KB n = 8
29 Correct 2 ms 376 KB n = 16
30 Correct 2 ms 376 KB n = 16
31 Correct 2 ms 376 KB n = 16
32 Correct 2 ms 376 KB n = 16
33 Correct 2 ms 376 KB n = 16
34 Correct 2 ms 376 KB n = 16
35 Correct 2 ms 376 KB n = 16
36 Correct 2 ms 376 KB n = 15
37 Correct 2 ms 376 KB n = 8
38 Correct 2 ms 352 KB n = 16
39 Correct 3 ms 376 KB n = 16
40 Correct 2 ms 376 KB n = 9
41 Correct 2 ms 376 KB n = 16
42 Correct 2 ms 376 KB n = 16
43 Correct 2 ms 376 KB n = 16
44 Correct 3 ms 376 KB n = 9
45 Correct 2 ms 376 KB n = 15
46 Correct 2 ms 376 KB n = 16
47 Correct 2 ms 376 KB n = 16
48 Correct 2 ms 376 KB n = 16
49 Correct 1368 ms 69224 KB n = 199999
50 Correct 1410 ms 69344 KB n = 199991
51 Correct 1377 ms 69244 KB n = 199993
52 Correct 996 ms 52904 KB n = 152076
53 Correct 546 ms 32512 KB n = 93249
54 Correct 1138 ms 57304 KB n = 199910
55 Correct 1176 ms 67936 KB n = 199999
56 Correct 1052 ms 57816 KB n = 199997
57 Correct 1150 ms 59448 KB n = 171294
58 Correct 917 ms 48936 KB n = 140872
59 Correct 1142 ms 58456 KB n = 199886
60 Correct 1208 ms 68356 KB n = 199996
61 Correct 1057 ms 60376 KB n = 200000
62 Correct 1071 ms 68312 KB n = 199998
63 Correct 1078 ms 67652 KB n = 200000
64 Correct 1212 ms 69780 KB n = 199998
65 Correct 1675 ms 69832 KB n = 200000
66 Correct 1682 ms 66300 KB n = 190000
67 Correct 1264 ms 62216 KB n = 177777
68 Correct 526 ms 35392 KB n = 100000
69 Correct 1234 ms 69852 KB n = 200000
70 Correct 1332 ms 69712 KB n = 200000
71 Correct 1373 ms 69864 KB n = 200000
72 Correct 1399 ms 73248 KB n = 200000
73 Correct 1371 ms 73176 KB n = 200000
74 Correct 1419 ms 73204 KB n = 200000
75 Correct 1447 ms 73432 KB n = 200000
76 Correct 1365 ms 73176 KB n = 200000
77 Correct 729 ms 38904 KB n = 200000
78 Correct 683 ms 38872 KB n = 200000
79 Correct 1587 ms 67288 KB n = 184307
80 Correct 500 ms 28064 KB n = 76040
81 Correct 1237 ms 61124 KB n = 199981
82 Correct 1140 ms 71640 KB n = 199994
83 Correct 1120 ms 63192 KB n = 199996
84 Correct 1137 ms 71512 KB n = 199998
85 Correct 1078 ms 70480 KB n = 200000
86 Correct 1132 ms 72920 KB n = 199998
87 Correct 1333 ms 73176 KB n = 200000
88 Correct 1312 ms 73132 KB n = 200000
89 Correct 1384 ms 73216 KB n = 200000
90 Correct 1279 ms 73048 KB n = 200000
91 Correct 1254 ms 73408 KB n = 200000
92 Correct 1359 ms 73176 KB n = 200000