oj.uz

Submission #404570

# Submission time Handle Problem Language Result Execution time Memory
404570 2021-05-14T16:07:28 Z MDario Roller Coaster Railroad (IOI16_railroad) C++11
100 / 100
 1364 ms 103044 KB 
#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int) s.size();
    vector<pair<ll, ll>> v1, v, g[400003];
    for(int i=0; i<n; i++){
        v1.push_back({s[i], 1});
        v1.push_back({t[i], -1});
    }
    v1.push_back({1, -1});
    v1.push_back({1e9, 1});
    sort(v1.begin(), v1.end());
    for(int i=0; i<v1.size(); i++){
        if(i==0||v1[i].F!=v1[i-1].F)v.push_back({v1[i].F, 0ll});
        v.back().S+=v1[i].S;
    }
    map<ll, ll> m;
    for(int i=0; i<v.size(); i++){
        m[v[i].F]=i;
    }
    ll r=0;
    for(int i=0; i<v.size()-1; i++){
        if(i!=0)v[i].S+=v[i-1].S;
        r+=(v[i+1].F-v[i].F)*max(0ll, v[i].S);
        if(v[i].S==0){
            g[i].push_back({i+1, (v[i+1].F-v[i].F)});
            g[i+1].push_back({i, (v[i+1].F-v[i].F)});
        }
        else{
            g[i].push_back({i+1, 0});
            g[i+1].push_back({i, 0});
        }
    }
    for(int i=0; i<n; i++){
        g[m[s[i]]].push_back({m[t[i]], 0});
        g[m[t[i]]].push_back({m[s[i]], 0});
    }
    g[m[1]].push_back({m[1e9], 0});
    g[m[1e9]].push_back({m[1], 0});
    priority_queue<pair<ll, ll>> q;
    ll a=v.size();
    bool b[a+1];
    for(int i=0; i<=a; i++){
        b[i]=0;
    }
    q.push({0, 0});
    pair<ll, ll> t1;
    while(!q.empty()){
        t1=q.top();
        q.pop();
        if(b[t1.S])continue;
        b[t1.S]=1;
        r-=t1.F;
        for(auto i : g[t1.S]){
            q.push({-i.S, i.F});
        }
    }
    return r;
}

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0; i<v1.size(); i++){
      |                  ~^~~~~~~~~~
railroad.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~
railroad.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0; i<v.size()-1; i++){
      |                  ~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB n = 2
2 Correct 6 ms 9676 KB n = 2
3 Correct 6 ms 9676 KB n = 2
4 Correct 6 ms 9676 KB n = 2
5 Correct 6 ms 9680 KB n = 2
6 Correct 7 ms 9676 KB n = 2
7 Correct 6 ms 9676 KB n = 3
8 Correct 6 ms 9676 KB n = 3
9 Correct 6 ms 9676 KB n = 3
10 Correct 6 ms 9676 KB n = 8
11 Correct 6 ms 9676 KB n = 8
12 Correct 6 ms 9676 KB n = 8
13 Correct 7 ms 9604 KB n = 8
14 Correct 7 ms 9632 KB n = 8
15 Correct 7 ms 9676 KB n = 8
16 Correct 6 ms 9644 KB n = 8
17 Correct 7 ms 9640 KB n = 8
18 Correct 8 ms 9676 KB n = 8
19 Correct 6 ms 9688 KB n = 3
20 Correct 7 ms 9676 KB n = 7
21 Correct 6 ms 9644 KB n = 8
22 Correct 6 ms 9676 KB n = 8
23 Correct 7 ms 9676 KB n = 8
24 Correct 7 ms 9688 KB n = 8
25 Correct 7 ms 9676 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB n = 2
2 Correct 6 ms 9676 KB n = 2
3 Correct 6 ms 9676 KB n = 2
4 Correct 6 ms 9676 KB n = 2
5 Correct 6 ms 9680 KB n = 2
6 Correct 7 ms 9676 KB n = 2
7 Correct 6 ms 9676 KB n = 3
8 Correct 6 ms 9676 KB n = 3
9 Correct 6 ms 9676 KB n = 3
10 Correct 6 ms 9676 KB n = 8
11 Correct 6 ms 9676 KB n = 8
12 Correct 6 ms 9676 KB n = 8
13 Correct 7 ms 9604 KB n = 8
14 Correct 7 ms 9632 KB n = 8
15 Correct 7 ms 9676 KB n = 8
16 Correct 6 ms 9644 KB n = 8
17 Correct 7 ms 9640 KB n = 8
18 Correct 8 ms 9676 KB n = 8
19 Correct 6 ms 9688 KB n = 3
20 Correct 7 ms 9676 KB n = 7
21 Correct 6 ms 9644 KB n = 8
22 Correct 6 ms 9676 KB n = 8
23 Correct 7 ms 9676 KB n = 8
24 Correct 7 ms 9688 KB n = 8
25 Correct 7 ms 9676 KB n = 8
26 Correct 7 ms 9676 KB n = 8
27 Correct 6 ms 9692 KB n = 8
28 Correct 7 ms 9676 KB n = 8
29 Correct 6 ms 9688 KB n = 16
30 Correct 6 ms 9620 KB n = 16
31 Correct 7 ms 9676 KB n = 16
32 Correct 6 ms 9676 KB n = 16
33 Correct 7 ms 9676 KB n = 16
34 Correct 7 ms 9676 KB n = 16
35 Correct 6 ms 9676 KB n = 16
36 Correct 6 ms 9676 KB n = 15
37 Correct 7 ms 9640 KB n = 8
38 Correct 6 ms 9676 KB n = 16
39 Correct 7 ms 9640 KB n = 16
40 Correct 6 ms 9636 KB n = 9
41 Correct 6 ms 9640 KB n = 16
42 Correct 7 ms 9676 KB n = 16
43 Correct 6 ms 9676 KB n = 16
44 Correct 7 ms 9676 KB n = 9
45 Correct 6 ms 9628 KB n = 15
46 Correct 6 ms 9640 KB n = 16
47 Correct 6 ms 9676 KB n = 16
48 Correct 7 ms 9676 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1208 ms 90560 KB n = 199999
2 Correct 1266 ms 94268 KB n = 199991
3 Correct 1244 ms 94344 KB n = 199993
4 Correct 914 ms 74248 KB n = 152076
5 Correct 486 ms 49360 KB n = 93249
6 Correct 992 ms 77728 KB n = 199910
7 Correct 1014 ms 88332 KB n = 199999
8 Correct 950 ms 78100 KB n = 199997
9 Correct 1075 ms 80636 KB n = 171294
10 Correct 863 ms 70240 KB n = 140872
11 Correct 1100 ms 78588 KB n = 199886
12 Correct 1080 ms 90408 KB n = 199996
13 Correct 1006 ms 82084 KB n = 200000
14 Correct 1083 ms 95204 KB n = 199998
15 Correct 1105 ms 94388 KB n = 200000
16 Correct 1086 ms 96832 KB n = 199998
17 Correct 1179 ms 102900 KB n = 200000
18 Correct 1195 ms 87572 KB n = 190000
19 Correct 1078 ms 88404 KB n = 177777
20 Correct 511 ms 50648 KB n = 100000
21 Correct 1134 ms 91540 KB n = 200000
22 Correct 1170 ms 93952 KB n = 200000
23 Correct 1261 ms 103032 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB n = 2
2 Correct 6 ms 9676 KB n = 2
3 Correct 6 ms 9676 KB n = 2
4 Correct 6 ms 9676 KB n = 2
5 Correct 6 ms 9680 KB n = 2
6 Correct 7 ms 9676 KB n = 2
7 Correct 6 ms 9676 KB n = 3
8 Correct 6 ms 9676 KB n = 3
9 Correct 6 ms 9676 KB n = 3
10 Correct 6 ms 9676 KB n = 8
11 Correct 6 ms 9676 KB n = 8
12 Correct 6 ms 9676 KB n = 8
13 Correct 7 ms 9604 KB n = 8
14 Correct 7 ms 9632 KB n = 8
15 Correct 7 ms 9676 KB n = 8
16 Correct 6 ms 9644 KB n = 8
17 Correct 7 ms 9640 KB n = 8
18 Correct 8 ms 9676 KB n = 8
19 Correct 6 ms 9688 KB n = 3
20 Correct 7 ms 9676 KB n = 7
21 Correct 6 ms 9644 KB n = 8
22 Correct 6 ms 9676 KB n = 8
23 Correct 7 ms 9676 KB n = 8
24 Correct 7 ms 9688 KB n = 8
25 Correct 7 ms 9676 KB n = 8
26 Correct 7 ms 9676 KB n = 8
27 Correct 6 ms 9692 KB n = 8
28 Correct 7 ms 9676 KB n = 8
29 Correct 6 ms 9688 KB n = 16
30 Correct 6 ms 9620 KB n = 16
31 Correct 7 ms 9676 KB n = 16
32 Correct 6 ms 9676 KB n = 16
33 Correct 7 ms 9676 KB n = 16
34 Correct 7 ms 9676 KB n = 16
35 Correct 6 ms 9676 KB n = 16
36 Correct 6 ms 9676 KB n = 15
37 Correct 7 ms 9640 KB n = 8
38 Correct 6 ms 9676 KB n = 16
39 Correct 7 ms 9640 KB n = 16
40 Correct 6 ms 9636 KB n = 9
41 Correct 6 ms 9640 KB n = 16
42 Correct 7 ms 9676 KB n = 16
43 Correct 6 ms 9676 KB n = 16
44 Correct 7 ms 9676 KB n = 9
45 Correct 6 ms 9628 KB n = 15
46 Correct 6 ms 9640 KB n = 16
47 Correct 6 ms 9676 KB n = 16
48 Correct 7 ms 9676 KB n = 16
49 Correct 1208 ms 90560 KB n = 199999
50 Correct 1266 ms 94268 KB n = 199991
51 Correct 1244 ms 94344 KB n = 199993
52 Correct 914 ms 74248 KB n = 152076
53 Correct 486 ms 49360 KB n = 93249
54 Correct 992 ms 77728 KB n = 199910
55 Correct 1014 ms 88332 KB n = 199999
56 Correct 950 ms 78100 KB n = 199997
57 Correct 1075 ms 80636 KB n = 171294
58 Correct 863 ms 70240 KB n = 140872
59 Correct 1100 ms 78588 KB n = 199886
60 Correct 1080 ms 90408 KB n = 199996
61 Correct 1006 ms 82084 KB n = 200000
62 Correct 1083 ms 95204 KB n = 199998
63 Correct 1105 ms 94388 KB n = 200000
64 Correct 1086 ms 96832 KB n = 199998
65 Correct 1179 ms 102900 KB n = 200000
66 Correct 1195 ms 87572 KB n = 190000
67 Correct 1078 ms 88404 KB n = 177777
68 Correct 511 ms 50648 KB n = 100000
69 Correct 1134 ms 91540 KB n = 200000
70 Correct 1170 ms 93952 KB n = 200000
71 Correct 1261 ms 103032 KB n = 200000
72 Correct 1364 ms 94148 KB n = 200000
73 Correct 1267 ms 94260 KB n = 200000
74 Correct 1250 ms 94368 KB n = 200000
75 Correct 1319 ms 97892 KB n = 200000
76 Correct 1237 ms 98092 KB n = 200000
77 Correct 637 ms 56768 KB n = 200000
78 Correct 633 ms 56728 KB n = 200000
79 Correct 1190 ms 85932 KB n = 184307
80 Correct 392 ms 42200 KB n = 76040
81 Correct 1094 ms 78668 KB n = 199981
82 Correct 1123 ms 90312 KB n = 199994
83 Correct 1024 ms 82032 KB n = 199996
84 Correct 1130 ms 95256 KB n = 199998
85 Correct 1153 ms 94372 KB n = 200000
86 Correct 1184 ms 96928 KB n = 199998
87 Correct 1314 ms 102964 KB n = 200000
88 Correct 1301 ms 92232 KB n = 200000
89 Correct 1307 ms 97932 KB n = 200000
90 Correct 1172 ms 91680 KB n = 200000
91 Correct 1239 ms 93924 KB n = 200000
92 Correct 1321 ms 103044 KB n = 200000