oj.uz

Submission #1070357

# Submission time Handle Problem Language Result Execution time Memory
1070357 2024-08-22T13:35:48 Z amirhoseinfar1385 Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 150 ms 38688 KB 
#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=600000+10;
vector<long long>allind;
long long n,vorod[maxn],khoroj[maxn],inf=1e9+5;

struct dsu{
    long long par[maxn];
    dsu(){
        for(long long i=0;i<maxn;i++){
            par[i]=i;
        }
    }
    long long root(long long u){
        if(u==par[u]){
            return u;
        }
        return par[u]=root(par[u]);
    }
    long long con(long long u,long long v){
        u=root(u);v=root(v);
        if(u==v){
            return 0;
        }
        par[u]=v;
        return 1;
    }
}ds,ds2;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    s.push_back(inf);
    t.push_back(1);
    n=(long long)s.size();
    for(long long i=0;i<n;i++){
        allind.push_back(s[i]);
        allind.push_back(t[i]);
    }
    sort(allind.begin(),allind.end());
    allind.resize(unique(allind.begin(),allind.end())-allind.begin());
    for(long long i=0;i<n;i++){
        long long pp=lower_bound(allind.begin(),allind.end(),s[i])-allind.begin();
        khoroj[pp]++;
        long long p=lower_bound(allind.begin(),allind.end(),t[i])-allind.begin();
        vorod[p]++;
        ds.con(p,pp);
    }
    long long mainres=0,vo=0,ko=0;
    for(long long i=0;i<(long long)allind.size();i++){
        ko+=khoroj[i];
        vo+=vorod[i];
        if(ko>vo){
            mainres+=(ko-vo)*(allind[i+1]-allind[i]);
        }
        if(ko!=vo){
            ds.con(i,i+1);
        }
    }
    vector<pair<long long ,pair<long long ,long long>>>allv;
    for(long long i=0;i<(long long)allind.size()-1;i++){
        if(ds.root(i)!=ds.root(i+1)){
            allv.push_back(make_pair(allind[i+1]-allind[i],make_pair(ds.root(i),ds.root(i+1))));
        }
    }
    sort(allv.begin(),allv.end());
    for(long long i=0;i<(long long)allv.size();i++){
        if(ds2.con(allv[i].second.first,allv[i].second.second)){
            mainres+=allv[i].first;
        }
    }
    return mainres;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 29224 KB n = 199999
2 Correct 150 ms 29352 KB n = 199991
3 Correct 129 ms 28716 KB n = 199993
4 Correct 93 ms 24224 KB n = 152076
5 Correct 57 ms 21300 KB n = 93249
6 Correct 117 ms 28716 KB n = 199910
7 Correct 110 ms 28508 KB n = 199999
8 Correct 106 ms 28196 KB n = 199997
9 Correct 110 ms 27940 KB n = 171294
10 Correct 90 ms 23936 KB n = 140872
11 Correct 112 ms 27772 KB n = 199886
12 Correct 111 ms 28968 KB n = 199996
13 Correct 107 ms 28456 KB n = 200000
14 Correct 111 ms 31272 KB n = 199998
15 Correct 111 ms 30760 KB n = 200000
16 Correct 115 ms 31436 KB n = 199998
17 Correct 113 ms 31276 KB n = 200000
18 Correct 116 ms 28284 KB n = 190000
19 Correct 100 ms 27868 KB n = 177777
20 Correct 57 ms 21816 KB n = 100000
21 Correct 117 ms 28464 KB n = 200000
22 Correct 141 ms 37420 KB n = 200000
23 Correct 120 ms 28460 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB n = 2
2 Correct 3 ms 12892 KB n = 2
3 Correct 2 ms 12920 KB n = 2
4 Correct 2 ms 12888 KB n = 2
5 Correct 2 ms 12892 KB n = 2
6 Correct 2 ms 12888 KB n = 2
7 Correct 2 ms 12892 KB n = 3
8 Correct 2 ms 12892 KB n = 3
9 Correct 2 ms 12892 KB n = 3
10 Correct 2 ms 12892 KB n = 8
11 Correct 2 ms 12892 KB n = 8
12 Correct 2 ms 12892 KB n = 8
13 Correct 2 ms 12892 KB n = 8
14 Correct 2 ms 12892 KB n = 8
15 Correct 2 ms 12888 KB n = 8
16 Correct 2 ms 12892 KB n = 8
17 Correct 2 ms 12892 KB n = 8
18 Correct 2 ms 12888 KB n = 8
19 Correct 2 ms 12892 KB n = 3
20 Correct 2 ms 12892 KB n = 7
21 Correct 2 ms 12892 KB n = 8
22 Correct 2 ms 12892 KB n = 8
23 Correct 3 ms 12888 KB n = 8
24 Correct 2 ms 12892 KB n = 8
25 Correct 2 ms 12924 KB n = 8
26 Correct 3 ms 12892 KB n = 8
27 Correct 2 ms 12728 KB n = 8
28 Correct 2 ms 12892 KB n = 8
29 Correct 2 ms 12892 KB n = 16
30 Correct 2 ms 12924 KB n = 16
31 Correct 2 ms 12908 KB n = 16
32 Correct 2 ms 12892 KB n = 16
33 Correct 2 ms 12892 KB n = 16
34 Correct 2 ms 12892 KB n = 16
35 Correct 2 ms 12888 KB n = 16
36 Correct 2 ms 12892 KB n = 15
37 Correct 2 ms 12892 KB n = 8
38 Correct 2 ms 12888 KB n = 16
39 Correct 2 ms 12892 KB n = 16
40 Correct 2 ms 12892 KB n = 9
41 Correct 2 ms 12892 KB n = 16
42 Correct 2 ms 12892 KB n = 16
43 Correct 2 ms 12888 KB n = 16
44 Correct 1 ms 12892 KB n = 9
45 Correct 1 ms 12892 KB n = 15
46 Correct 2 ms 12892 KB n = 16
47 Correct 2 ms 12888 KB n = 16
48 Correct 2 ms 12892 KB n = 16
49 Correct 131 ms 29224 KB n = 199999
50 Correct 150 ms 29352 KB n = 199991
51 Correct 129 ms 28716 KB n = 199993
52 Correct 93 ms 24224 KB n = 152076
53 Correct 57 ms 21300 KB n = 93249
54 Correct 117 ms 28716 KB n = 199910
55 Correct 110 ms 28508 KB n = 199999
56 Correct 106 ms 28196 KB n = 199997
57 Correct 110 ms 27940 KB n = 171294
58 Correct 90 ms 23936 KB n = 140872
59 Correct 112 ms 27772 KB n = 199886
60 Correct 111 ms 28968 KB n = 199996
61 Correct 107 ms 28456 KB n = 200000
62 Correct 111 ms 31272 KB n = 199998
63 Correct 111 ms 30760 KB n = 200000
64 Correct 115 ms 31436 KB n = 199998
65 Correct 113 ms 31276 KB n = 200000
66 Correct 116 ms 28284 KB n = 190000
67 Correct 100 ms 27868 KB n = 177777
68 Correct 57 ms 21816 KB n = 100000
69 Correct 117 ms 28464 KB n = 200000
70 Correct 141 ms 37420 KB n = 200000
71 Correct 120 ms 28460 KB n = 200000
72 Correct 124 ms 30244 KB n = 200000
73 Correct 134 ms 30248 KB n = 200000
74 Correct 130 ms 30240 KB n = 200000
75 Correct 121 ms 30248 KB n = 200000
76 Correct 113 ms 28200 KB n = 200000
77 Correct 97 ms 30576 KB n = 200000
78 Correct 125 ms 36392 KB n = 200000
79 Correct 116 ms 29096 KB n = 184307
80 Correct 47 ms 21032 KB n = 76040
81 Correct 116 ms 29740 KB n = 199981
82 Correct 114 ms 29996 KB n = 199994
83 Correct 111 ms 29744 KB n = 199996
84 Correct 110 ms 32532 KB n = 199998
85 Correct 111 ms 32044 KB n = 200000
86 Correct 115 ms 32296 KB n = 199998
87 Correct 113 ms 33068 KB n = 200000
88 Correct 123 ms 31528 KB n = 200000
89 Correct 114 ms 30836 KB n = 200000
90 Correct 126 ms 30328 KB n = 200000
91 Correct 140 ms 38688 KB n = 200000
92 Correct 121 ms 31016 KB n = 200000