oj.uz

Submission #576727

# Submission time Handle Problem Language Result Execution time Memory
576727 2022-06-13T11:10:22 Z eecs Shopping Plans (CCO20_day2problem3) C++17
25 / 25
 375 ms 47920 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 200010;
int n, m, K, id[maxn];
ll ans;

struct {
    int l, r;
    vector<int> c;
    vector<ll> w;
    priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<>> Q;

    bool init() {
        if (l > c.size()) return 1;
        sort(c.begin(), c.end());
        r = min(r, (int)c.size());
        if (!r) return w = {0}, 0;
        if (!l) w = {0};
        ans += accumulate(c.begin(), c.begin() + l, 0LL);
        ll s = 0;
        for (int i = l; i < r; i++) {
            if (i) Q.emplace(s, i - 1, i, c.size() + 1);
            s += c[i];
        }
        Q.emplace(s, r - 1, r, c.size() + 1);
        return 0;
    }
    void inc() {
        if (Q.empty()) return w.push_back(1e18);
        auto p = Q.top(); Q.pop();
        w.push_back(get<0>(p));
        if (get<2>(p) + 1 < get<3>(p)) {
            Q.emplace(get<0>(p) + c[get<2>(p)] - c[get<2>(p) - 1], get<1>(p), get<2>(p) + 1, get<3>(p));
        }
        if (get<1>(p) && get<1>(p) + 1 < get<2>(p)) {
            Q.emplace(get<0>(p) + c[get<1>(p)] - c[get<1>(p) - 1], get<1>(p) - 1, get<1>(p) + 1, get<2>(p));
        }
    }
    ll operator [] (int k) {
        while (k >= w.size()) inc();
        return w[k];
    }
} V[maxn];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> K;
    while (n--) {
        int x, y;
        cin >> x >> y;
        V[x].c.push_back(y);
    }
    for (int i = 1; i <= m; i++) {
        cin >> V[i].l >> V[i].r;
        if (V[i].init()) {
            while (K--) cout << "-1\n";
            exit(0);
        }
    }
    iota(id + 1, id + m + 1, 1);
    sort(id + 1, id + m + 1, [&](int i, int j) -> bool {
        return V[i][1] - V[i][0] < V[j][1] - V[j][0];
    });
    cout << ans << "\n", K--;
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> Q;
    Q.emplace(V[id[1]][1] - V[id[1]][0], 1, 2);
    while (K && !Q.empty()) {
        auto p = Q.top(); Q.pop();
        if (get<0>(p) > 1e17) break;
        cout << ans + get<0>(p) << "\n", K--;
        int x = id[get<1>(p)], y = id[get<1>(p) + 1];
        Q.emplace(get<0>(p) + V[x][get<2>(p)] - V[x][get<2>(p) - 1], get<1>(p), get<2>(p) + 1);
        if (get<1>(p) < m) {
            Q.emplace(get<0>(p) + V[y][1] - V[y][0], get<1>(p) + 1, 2);
            if (get<2>(p) == 2) Q.emplace(get<0>(p) + V[y][1] - V[y][0] - V[x][1] + V[x][0], get<1>(p) + 1, 2);
        }
    }
    while (K--) cout << "-1\n";
    return 0;
}

Compilation message

Main.cpp: In member function 'bool<unnamed struct>::init()':
Main.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         if (l > c.size()) return 1;
      |             ~~^~~~~~~~~~
Main.cpp: In member function 'll<unnamed struct>::operator[](int)':
Main.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while (k >= w.size()) inc();
      |                ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 18196 KB Output is correct
2 Correct 12 ms 18016 KB Output is correct
3 Correct 13 ms 18068 KB Output is correct
4 Correct 12 ms 17960 KB Output is correct
5 Correct 12 ms 18132 KB Output is correct
6 Correct 12 ms 18084 KB Output is correct
7 Correct 11 ms 17876 KB Output is correct
8 Correct 14 ms 17864 KB Output is correct
9 Correct 10 ms 17640 KB Output is correct
10 Correct 12 ms 18164 KB Output is correct
11 Correct 12 ms 17636 KB Output is correct
12 Correct 10 ms 17788 KB Output is correct
13 Correct 10 ms 17852 KB Output is correct
14 Correct 12 ms 18132 KB Output is correct
15 Correct 10 ms 17812 KB Output is correct
16 Correct 10 ms 17744 KB Output is correct
17 Correct 12 ms 17948 KB Output is correct
18 Correct 11 ms 17748 KB Output is correct
19 Correct 11 ms 17748 KB Output is correct
20 Correct 13 ms 18164 KB Output is correct
21 Correct 10 ms 17748 KB Output is correct
22 Correct 10 ms 17748 KB Output is correct
23 Correct 11 ms 17812 KB Output is correct
24 Correct 11 ms 17620 KB Output is correct
25 Correct 11 ms 17620 KB Output is correct
26 Correct 13 ms 18004 KB Output is correct
27 Correct 12 ms 17876 KB Output is correct
28 Correct 11 ms 17748 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 27128 KB Output is correct
2 Correct 85 ms 27036 KB Output is correct
3 Correct 68 ms 27156 KB Output is correct
4 Correct 69 ms 27112 KB Output is correct
5 Correct 69 ms 27200 KB Output is correct
6 Correct 71 ms 27184 KB Output is correct
7 Correct 67 ms 26888 KB Output is correct
8 Correct 64 ms 26748 KB Output is correct
9 Correct 15 ms 18252 KB Output is correct
10 Correct 68 ms 27072 KB Output is correct
11 Correct 19 ms 18212 KB Output is correct
12 Correct 40 ms 22316 KB Output is correct
13 Correct 72 ms 26748 KB Output is correct
14 Correct 66 ms 27108 KB Output is correct
15 Correct 16 ms 18392 KB Output is correct
16 Correct 72 ms 26692 KB Output is correct
17 Correct 71 ms 27128 KB Output is correct
18 Correct 27 ms 20164 KB Output is correct
19 Correct 80 ms 26792 KB Output is correct
20 Correct 74 ms 27164 KB Output is correct
21 Correct 15 ms 18520 KB Output is correct
22 Correct 79 ms 26660 KB Output is correct
23 Correct 63 ms 26596 KB Output is correct
24 Correct 15 ms 18212 KB Output is correct
25 Correct 14 ms 18260 KB Output is correct
26 Correct 69 ms 27244 KB Output is correct
27 Correct 67 ms 27108 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 18196 KB Output is correct
2 Correct 12 ms 18016 KB Output is correct
3 Correct 13 ms 18068 KB Output is correct
4 Correct 12 ms 17960 KB Output is correct
5 Correct 12 ms 18132 KB Output is correct
6 Correct 12 ms 18084 KB Output is correct
7 Correct 11 ms 17876 KB Output is correct
8 Correct 14 ms 17864 KB Output is correct
9 Correct 10 ms 17640 KB Output is correct
10 Correct 12 ms 18164 KB Output is correct
11 Correct 12 ms 17636 KB Output is correct
12 Correct 10 ms 17788 KB Output is correct
13 Correct 10 ms 17852 KB Output is correct
14 Correct 12 ms 18132 KB Output is correct
15 Correct 10 ms 17812 KB Output is correct
16 Correct 10 ms 17744 KB Output is correct
17 Correct 12 ms 17948 KB Output is correct
18 Correct 11 ms 17748 KB Output is correct
19 Correct 11 ms 17748 KB Output is correct
20 Correct 13 ms 18164 KB Output is correct
21 Correct 10 ms 17748 KB Output is correct
22 Correct 10 ms 17748 KB Output is correct
23 Correct 11 ms 17812 KB Output is correct
24 Correct 11 ms 17620 KB Output is correct
25 Correct 11 ms 17620 KB Output is correct
26 Correct 13 ms 18004 KB Output is correct
27 Correct 12 ms 17876 KB Output is correct
28 Correct 11 ms 17748 KB Output is correct
29 Correct 69 ms 27128 KB Output is correct
30 Correct 85 ms 27036 KB Output is correct
31 Correct 68 ms 27156 KB Output is correct
32 Correct 69 ms 27112 KB Output is correct
33 Correct 69 ms 27200 KB Output is correct
34 Correct 71 ms 27184 KB Output is correct
35 Correct 67 ms 26888 KB Output is correct
36 Correct 64 ms 26748 KB Output is correct
37 Correct 15 ms 18252 KB Output is correct
38 Correct 68 ms 27072 KB Output is correct
39 Correct 19 ms 18212 KB Output is correct
40 Correct 40 ms 22316 KB Output is correct
41 Correct 72 ms 26748 KB Output is correct
42 Correct 66 ms 27108 KB Output is correct
43 Correct 16 ms 18392 KB Output is correct
44 Correct 72 ms 26692 KB Output is correct
45 Correct 71 ms 27128 KB Output is correct
46 Correct 27 ms 20164 KB Output is correct
47 Correct 80 ms 26792 KB Output is correct
48 Correct 74 ms 27164 KB Output is correct
49 Correct 15 ms 18520 KB Output is correct
50 Correct 79 ms 26660 KB Output is correct
51 Correct 63 ms 26596 KB Output is correct
52 Correct 15 ms 18212 KB Output is correct
53 Correct 14 ms 18260 KB Output is correct
54 Correct 69 ms 27244 KB Output is correct
55 Correct 67 ms 27108 KB Output is correct
56 Correct 250 ms 43756 KB Output is correct
57 Correct 207 ms 39364 KB Output is correct
58 Correct 233 ms 41268 KB Output is correct
59 Correct 148 ms 36316 KB Output is correct
60 Correct 261 ms 44488 KB Output is correct
61 Correct 231 ms 39940 KB Output is correct
62 Correct 140 ms 33256 KB Output is correct
63 Correct 108 ms 30192 KB Output is correct
64 Correct 72 ms 24252 KB Output is correct
65 Correct 214 ms 39196 KB Output is correct
66 Correct 75 ms 24244 KB Output is correct
67 Correct 67 ms 27352 KB Output is correct
68 Correct 72 ms 27412 KB Output is correct
69 Correct 229 ms 41196 KB Output is correct
70 Correct 17 ms 18772 KB Output is correct
71 Correct 74 ms 27684 KB Output is correct
72 Correct 152 ms 36304 KB Output is correct
73 Correct 16 ms 18380 KB Output is correct
74 Correct 74 ms 27516 KB Output is correct
75 Correct 265 ms 44480 KB Output is correct
76 Correct 15 ms 18260 KB Output is correct
77 Correct 71 ms 27352 KB Output is correct
78 Correct 109 ms 30504 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 26568 KB Output is correct
2 Correct 59 ms 26456 KB Output is correct
3 Correct 17 ms 18452 KB Output is correct
4 Correct 15 ms 18516 KB Output is correct
5 Correct 326 ms 44920 KB Output is correct
6 Correct 309 ms 43924 KB Output is correct
7 Correct 330 ms 44268 KB Output is correct
8 Correct 257 ms 43432 KB Output is correct
9 Correct 308 ms 45144 KB Output is correct
10 Correct 312 ms 43768 KB Output is correct
11 Correct 245 ms 43568 KB Output is correct
12 Correct 215 ms 38504 KB Output is correct
13 Correct 233 ms 36588 KB Output is correct
14 Correct 322 ms 43840 KB Output is correct
15 Correct 310 ms 43952 KB Output is correct
16 Correct 72 ms 27308 KB Output is correct
17 Correct 73 ms 27004 KB Output is correct
18 Correct 353 ms 45484 KB Output is correct
19 Correct 66 ms 27840 KB Output is correct
20 Correct 75 ms 27124 KB Output is correct
21 Correct 271 ms 44416 KB Output is correct
22 Correct 68 ms 27200 KB Output is correct
23 Correct 71 ms 27032 KB Output is correct
24 Correct 375 ms 46424 KB Output is correct
25 Correct 58 ms 22984 KB Output is correct
26 Correct 60 ms 22916 KB Output is correct
27 Correct 242 ms 37752 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 18196 KB Output is correct
2 Correct 12 ms 18016 KB Output is correct
3 Correct 13 ms 18068 KB Output is correct
4 Correct 12 ms 17960 KB Output is correct
5 Correct 12 ms 18132 KB Output is correct
6 Correct 12 ms 18084 KB Output is correct
7 Correct 11 ms 17876 KB Output is correct
8 Correct 14 ms 17864 KB Output is correct
9 Correct 10 ms 17640 KB Output is correct
10 Correct 12 ms 18164 KB Output is correct
11 Correct 12 ms 17636 KB Output is correct
12 Correct 10 ms 17788 KB Output is correct
13 Correct 10 ms 17852 KB Output is correct
14 Correct 12 ms 18132 KB Output is correct
15 Correct 10 ms 17812 KB Output is correct
16 Correct 10 ms 17744 KB Output is correct
17 Correct 12 ms 17948 KB Output is correct
18 Correct 11 ms 17748 KB Output is correct
19 Correct 11 ms 17748 KB Output is correct
20 Correct 13 ms 18164 KB Output is correct
21 Correct 10 ms 17748 KB Output is correct
22 Correct 10 ms 17748 KB Output is correct
23 Correct 11 ms 17812 KB Output is correct
24 Correct 11 ms 17620 KB Output is correct
25 Correct 11 ms 17620 KB Output is correct
26 Correct 13 ms 18004 KB Output is correct
27 Correct 12 ms 17876 KB Output is correct
28 Correct 11 ms 17748 KB Output is correct
29 Correct 69 ms 27128 KB Output is correct
30 Correct 85 ms 27036 KB Output is correct
31 Correct 68 ms 27156 KB Output is correct
32 Correct 69 ms 27112 KB Output is correct
33 Correct 69 ms 27200 KB Output is correct
34 Correct 71 ms 27184 KB Output is correct
35 Correct 67 ms 26888 KB Output is correct
36 Correct 64 ms 26748 KB Output is correct
37 Correct 15 ms 18252 KB Output is correct
38 Correct 68 ms 27072 KB Output is correct
39 Correct 19 ms 18212 KB Output is correct
40 Correct 40 ms 22316 KB Output is correct
41 Correct 72 ms 26748 KB Output is correct
42 Correct 66 ms 27108 KB Output is correct
43 Correct 16 ms 18392 KB Output is correct
44 Correct 72 ms 26692 KB Output is correct
45 Correct 71 ms 27128 KB Output is correct
46 Correct 27 ms 20164 KB Output is correct
47 Correct 80 ms 26792 KB Output is correct
48 Correct 74 ms 27164 KB Output is correct
49 Correct 15 ms 18520 KB Output is correct
50 Correct 79 ms 26660 KB Output is correct
51 Correct 63 ms 26596 KB Output is correct
52 Correct 15 ms 18212 KB Output is correct
53 Correct 14 ms 18260 KB Output is correct
54 Correct 69 ms 27244 KB Output is correct
55 Correct 67 ms 27108 KB Output is correct
56 Correct 250 ms 43756 KB Output is correct
57 Correct 207 ms 39364 KB Output is correct
58 Correct 233 ms 41268 KB Output is correct
59 Correct 148 ms 36316 KB Output is correct
60 Correct 261 ms 44488 KB Output is correct
61 Correct 231 ms 39940 KB Output is correct
62 Correct 140 ms 33256 KB Output is correct
63 Correct 108 ms 30192 KB Output is correct
64 Correct 72 ms 24252 KB Output is correct
65 Correct 214 ms 39196 KB Output is correct
66 Correct 75 ms 24244 KB Output is correct
67 Correct 67 ms 27352 KB Output is correct
68 Correct 72 ms 27412 KB Output is correct
69 Correct 229 ms 41196 KB Output is correct
70 Correct 17 ms 18772 KB Output is correct
71 Correct 74 ms 27684 KB Output is correct
72 Correct 152 ms 36304 KB Output is correct
73 Correct 16 ms 18380 KB Output is correct
74 Correct 74 ms 27516 KB Output is correct
75 Correct 265 ms 44480 KB Output is correct
76 Correct 15 ms 18260 KB Output is correct
77 Correct 71 ms 27352 KB Output is correct
78 Correct 109 ms 30504 KB Output is correct
79 Correct 60 ms 26568 KB Output is correct
80 Correct 59 ms 26456 KB Output is correct
81 Correct 17 ms 18452 KB Output is correct
82 Correct 15 ms 18516 KB Output is correct
83 Correct 326 ms 44920 KB Output is correct
84 Correct 309 ms 43924 KB Output is correct
85 Correct 330 ms 44268 KB Output is correct
86 Correct 257 ms 43432 KB Output is correct
87 Correct 308 ms 45144 KB Output is correct
88 Correct 312 ms 43768 KB Output is correct
89 Correct 245 ms 43568 KB Output is correct
90 Correct 215 ms 38504 KB Output is correct
91 Correct 233 ms 36588 KB Output is correct
92 Correct 322 ms 43840 KB Output is correct
93 Correct 310 ms 43952 KB Output is correct
94 Correct 72 ms 27308 KB Output is correct
95 Correct 73 ms 27004 KB Output is correct
96 Correct 353 ms 45484 KB Output is correct
97 Correct 66 ms 27840 KB Output is correct
98 Correct 75 ms 27124 KB Output is correct
99 Correct 271 ms 44416 KB Output is correct
100 Correct 68 ms 27200 KB Output is correct
101 Correct 71 ms 27032 KB Output is correct
102 Correct 375 ms 46424 KB Output is correct
103 Correct 58 ms 22984 KB Output is correct
104 Correct 60 ms 22916 KB Output is correct
105 Correct 242 ms 37752 KB Output is correct
106 Correct 56 ms 22320 KB Output is correct
107 Correct 64 ms 26556 KB Output is correct
108 Correct 59 ms 22276 KB Output is correct
109 Correct 65 ms 26776 KB Output is correct
110 Correct 334 ms 47160 KB Output is correct
111 Correct 330 ms 45500 KB Output is correct
112 Correct 334 ms 46176 KB Output is correct
113 Correct 276 ms 44172 KB Output is correct
114 Correct 338 ms 47420 KB Output is correct
115 Correct 341 ms 45744 KB Output is correct
116 Correct 262 ms 43136 KB Output is correct
117 Correct 218 ms 43300 KB Output is correct
118 Correct 249 ms 40292 KB Output is correct
119 Correct 84 ms 24328 KB Output is correct
120 Correct 322 ms 45492 KB Output is correct
121 Correct 71 ms 27808 KB Output is correct
122 Correct 73 ms 27516 KB Output is correct
123 Correct 351 ms 46600 KB Output is correct
124 Correct 71 ms 27476 KB Output is correct
125 Correct 73 ms 27728 KB Output is correct
126 Correct 285 ms 44040 KB Output is correct
127 Correct 70 ms 27676 KB Output is correct
128 Correct 75 ms 27580 KB Output is correct
129 Correct 349 ms 47920 KB Output is correct
130 Correct 65 ms 28056 KB Output is correct
131 Correct 72 ms 28704 KB Output is correct
132 Correct 229 ms 37216 KB Output is correct