oj.uz

Submission #30581

# Submission time Handle Problem Language Result Execution time Memory
30581 2017-07-25T06:34:09 Z RayaBurong25_1 Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 939 ms 47984 KB 
#include "railroad.h"
#include <set>
#include <algorithm>
#define INF 1000000007
std::set<long long> I;
std::vector<long long> Ic;
long long Fen[400005];
int Pa[400005];
int n;
typedef struct node node;
struct node
{
    int u, v;
    long long w;
};
int compareW(node a, node b)
{
    return (a.w < b.w);
}
std::vector<node> E;
void update(int pos, int val)
{
    for (; pos <= Ic.size(); pos += pos&-pos)
        Fen[pos] += val;
}
long long query(int pos)
{
    long long r = 0;
    for (; pos > 0; pos -= pos&-pos)
        r += Fen[pos];
    return r;
}
int uf(int u)
{
    return (Pa[u] == 0)?u:(Pa[u] = uf(Pa[u]));
}
void join(int u, int v)
{
    // printf("Join %d (%d) %d (%d)\n", u, Ic[u - 1], v, Ic[v - 1]);
    int pu = uf(u);
    int pv = uf(v);
    if (pu != pv)
        Pa[pu] = pv;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    n = (int) s.size();
    int i;
    I.insert(1);
    I.insert(INF);
    for (i = 0; i < n; i++)
    {
        I.insert(s[i]);
        I.insert(t[i]);
    }
    std::set<long long>::iterator it;
    for (it = I.begin(); it != I.end(); it++)
        Ic.push_back(*it);
    int u, v;
    for (i = 0; i < n; i++)
    {
        u = std::lower_bound(Ic.begin(), Ic.end(), s[i]) - Ic.begin() + 1;
        v = std::lower_bound(Ic.begin(), Ic.end(), t[i]) - Ic.begin() + 1;
        update(u, 1);
        update(v, -1);
        join(u, v);
    }
    update(Ic.size(), 1);
    update(1, -1);
    join(Ic.size(), 1);
    long long r, Ans = 0;
    for (i = 1; i < Ic.size(); i++)
    {
        r = query(i);
        // printf("r%d\n", r);
        if (r > 0)
        {
            Ans += r*(Ic[i] - Ic[i - 1]);
        }
        if (r != 0)
        {
            join(i, i + 1);
        }
        E.push_back({i, i + 1, (Ic[i] - Ic[i - 1])});
    }
    std::sort(E.begin(), E.end(), compareW);
    int pu, pv;
    for (i = 0; i < E.size(); i++)
    {
        u = E[i].u;
        v = E[i].v;
        pu = uf(u);
        pv = uf(v);
        if (pu != pv)
        {
            // printf("Add %d (%d) %d (%d)\n", u, Ic[u - 1], v, Ic[v - 1]);
            Pa[pu] = pv;
            Ans += E[i].w;
        }
    }
    return Ans;
}

Compilation message

railroad.cpp: In function 'void update(int, int)':
railroad.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (; pos <= Ic.size(); pos += pos&-pos)
                ^
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < Ic.size(); i++)
                   ^
railroad.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < E.size(); i++)
                   ^

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 44980 KB n = 199999
2 Correct 826 ms 44980 KB n = 199991
3 Correct 606 ms 44980 KB n = 199993
4 Correct 446 ms 39716 KB n = 152076
5 Correct 229 ms 25120 KB n = 93249
6 Correct 573 ms 41568 KB n = 199910
7 Correct 453 ms 44568 KB n = 199999
8 Correct 429 ms 41688 KB n = 199997
9 Correct 509 ms 41832 KB n = 171294
10 Correct 566 ms 38512 KB n = 140872
11 Correct 609 ms 41828 KB n = 199886
12 Correct 633 ms 44692 KB n = 199996
13 Correct 639 ms 42412 KB n = 200000
14 Correct 499 ms 44600 KB n = 199998
15 Correct 693 ms 44292 KB n = 200000
16 Correct 716 ms 44904 KB n = 199998
17 Correct 606 ms 47980 KB n = 200000
18 Correct 576 ms 43984 KB n = 190000
19 Correct 583 ms 45196 KB n = 177777
20 Correct 216 ms 25852 KB n = 100000
21 Correct 556 ms 44984 KB n = 200000
22 Correct 653 ms 44988 KB n = 200000
23 Correct 639 ms 44988 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6628 KB n = 2
2 Correct 0 ms 6628 KB n = 2
3 Correct 0 ms 6628 KB n = 2
4 Correct 0 ms 6628 KB n = 2
5 Correct 0 ms 6628 KB n = 2
6 Correct 0 ms 6628 KB n = 2
7 Correct 0 ms 6628 KB n = 3
8 Correct 0 ms 6628 KB n = 3
9 Correct 0 ms 6628 KB n = 3
10 Correct 0 ms 6628 KB n = 8
11 Correct 0 ms 6628 KB n = 8
12 Correct 0 ms 6628 KB n = 8
13 Correct 0 ms 6628 KB n = 8
14 Correct 0 ms 6628 KB n = 8
15 Correct 0 ms 6628 KB n = 8
16 Correct 0 ms 6628 KB n = 8
17 Correct 0 ms 6628 KB n = 8
18 Correct 0 ms 6628 KB n = 8
19 Correct 0 ms 6628 KB n = 3
20 Correct 0 ms 6628 KB n = 7
21 Correct 0 ms 6628 KB n = 8
22 Correct 0 ms 6628 KB n = 8
23 Correct 0 ms 6628 KB n = 8
24 Correct 0 ms 6628 KB n = 8
25 Correct 0 ms 6628 KB n = 8
26 Correct 0 ms 6628 KB n = 8
27 Correct 0 ms 6628 KB n = 8
28 Correct 0 ms 6628 KB n = 8
29 Correct 0 ms 6628 KB n = 16
30 Correct 0 ms 6628 KB n = 16
31 Correct 0 ms 6628 KB n = 16
32 Correct 0 ms 6628 KB n = 16
33 Correct 0 ms 6628 KB n = 16
34 Correct 0 ms 6628 KB n = 16
35 Correct 0 ms 6628 KB n = 16
36 Correct 0 ms 6628 KB n = 15
37 Correct 0 ms 6628 KB n = 8
38 Correct 0 ms 6628 KB n = 16
39 Correct 0 ms 6628 KB n = 16
40 Correct 0 ms 6628 KB n = 9
41 Correct 0 ms 6628 KB n = 16
42 Correct 0 ms 6628 KB n = 16
43 Correct 0 ms 6628 KB n = 16
44 Correct 0 ms 6628 KB n = 9
45 Correct 0 ms 6628 KB n = 15
46 Correct 0 ms 6628 KB n = 16
47 Correct 0 ms 6628 KB n = 16
48 Correct 0 ms 6628 KB n = 16
49 Correct 786 ms 44980 KB n = 199999
50 Correct 826 ms 44980 KB n = 199991
51 Correct 606 ms 44980 KB n = 199993
52 Correct 446 ms 39716 KB n = 152076
53 Correct 229 ms 25120 KB n = 93249
54 Correct 573 ms 41568 KB n = 199910
55 Correct 453 ms 44568 KB n = 199999
56 Correct 429 ms 41688 KB n = 199997
57 Correct 509 ms 41832 KB n = 171294
58 Correct 566 ms 38512 KB n = 140872
59 Correct 609 ms 41828 KB n = 199886
60 Correct 633 ms 44692 KB n = 199996
61 Correct 639 ms 42412 KB n = 200000
62 Correct 499 ms 44600 KB n = 199998
63 Correct 693 ms 44292 KB n = 200000
64 Correct 716 ms 44904 KB n = 199998
65 Correct 606 ms 47980 KB n = 200000
66 Correct 576 ms 43984 KB n = 190000
67 Correct 583 ms 45196 KB n = 177777
68 Correct 216 ms 25852 KB n = 100000
69 Correct 556 ms 44984 KB n = 200000
70 Correct 653 ms 44988 KB n = 200000
71 Correct 639 ms 44988 KB n = 200000
72 Correct 763 ms 44984 KB n = 200000
73 Correct 939 ms 44984 KB n = 200000
74 Correct 893 ms 44984 KB n = 200000
75 Correct 759 ms 44984 KB n = 200000
76 Correct 629 ms 44984 KB n = 200000
77 Correct 309 ms 28364 KB n = 200000
78 Correct 339 ms 27420 KB n = 200000
79 Correct 816 ms 43244 KB n = 184307
80 Correct 279 ms 23236 KB n = 76040
81 Correct 726 ms 41832 KB n = 199981
82 Correct 619 ms 44684 KB n = 199994
83 Correct 746 ms 42424 KB n = 199996
84 Correct 453 ms 44592 KB n = 199998
85 Correct 449 ms 44296 KB n = 200000
86 Correct 503 ms 44900 KB n = 199998
87 Correct 576 ms 47984 KB n = 200000
88 Correct 589 ms 45528 KB n = 200000
89 Correct 809 ms 47984 KB n = 200000
90 Correct 826 ms 44984 KB n = 200000
91 Correct 663 ms 44988 KB n = 200000
92 Correct 579 ms 44988 KB n = 200000