oj.uz

Submission #259959

# Submission time Handle Problem Language Result Execution time Memory
259959 2020-08-08T21:02:25 Z keko37 Two Dishes (JOI19_dishes) C++14
100 / 100
 3560 ms 250500 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long llint;

const int MAXN = 1000005;
const llint INF = 1000000000000000000LL;

llint n, m, sol;
llint a[MAXN], b[MAXN], s[MAXN], t[MAXN], p[MAXN], q[MAXN];
llint suma[MAXN], sumb[MAXN], d[MAXN], lim[MAXN];
vector <int> v[MAXN], r;
set <int> st;

void upd (int pos) {
    llint ofs = 0;
    while (pos <= m) {
        int nxt = *st.upper_bound(pos);
        if (d[pos] - ofs > lim[pos]) {
            d[pos] -= ofs;
            break;
        }
        ofs += lim[pos] - d[pos];
        d[pos] = lim[pos];
        st.erase(pos);
        pos = nxt;
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> s[i] >> p[i];
        suma[i] = suma[i - 1] + a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i] >> t[i] >> q[i];
        sumb[i] = sumb[i - 1] + b[i];

        if (sumb[i] > t[i]) continue;
        d[i] = lim[i] = q[i];
        int ind = upper_bound(suma, suma + n + 1, t[i] - sumb[i]) - suma;
        v[ind].push_back(i);
    }
    st.insert(m + 1);
    for (int i = 1; i <= n; i++) {
        r.clear();
        if (suma[i] <= s[i]) {
            int ind = upper_bound(sumb, sumb + m + 1, s[i] - suma[i]) - sumb - 1;
            d[0] += p[i];
            d[ind + 1] -= p[i];
            st.insert(ind + 1); r.push_back(ind + 1);
        }
        for (auto x : v[i]) {
            lim[x] = 0;
            st.insert(x); r.push_back(x);
        }
        for (auto x : r) upd(x);
    }
    for (int i = 0; i <= m; i++) sol += d[i];
    cout << sol;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 51320 KB Output is correct
2 Correct 322 ms 43128 KB Output is correct
3 Correct 239 ms 40428 KB Output is correct
4 Correct 318 ms 47608 KB Output is correct
5 Correct 16 ms 23936 KB Output is correct
6 Correct 296 ms 42024 KB Output is correct
7 Correct 138 ms 33876 KB Output is correct
8 Correct 126 ms 30200 KB Output is correct
9 Correct 256 ms 40528 KB Output is correct
10 Correct 272 ms 45896 KB Output is correct
11 Correct 189 ms 40432 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 14 ms 23936 KB Output is correct
3 Correct 20 ms 23936 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 14 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 14 ms 23936 KB Output is correct
9 Correct 18 ms 23936 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 15 ms 23936 KB Output is correct
12 Correct 15 ms 23936 KB Output is correct
13 Correct 17 ms 23936 KB Output is correct
14 Correct 15 ms 23936 KB Output is correct
15 Correct 16 ms 23936 KB Output is correct
16 Correct 15 ms 23936 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 14 ms 23936 KB Output is correct
3 Correct 20 ms 23936 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 14 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 14 ms 23936 KB Output is correct
9 Correct 18 ms 23936 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 15 ms 23936 KB Output is correct
12 Correct 15 ms 23936 KB Output is correct
13 Correct 17 ms 23936 KB Output is correct
14 Correct 15 ms 23936 KB Output is correct
15 Correct 16 ms 23936 KB Output is correct
16 Correct 15 ms 23936 KB Output is correct
17 Correct 19 ms 24064 KB Output is correct
18 Correct 19 ms 24192 KB Output is correct
19 Correct 18 ms 24064 KB Output is correct
20 Correct 20 ms 24064 KB Output is correct
21 Correct 17 ms 24064 KB Output is correct
22 Correct 18 ms 24064 KB Output is correct
23 Correct 18 ms 24064 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 14 ms 23936 KB Output is correct
3 Correct 20 ms 23936 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 14 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 14 ms 23936 KB Output is correct
9 Correct 18 ms 23936 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 15 ms 23936 KB Output is correct
12 Correct 15 ms 23936 KB Output is correct
13 Correct 17 ms 23936 KB Output is correct
14 Correct 15 ms 23936 KB Output is correct
15 Correct 16 ms 23936 KB Output is correct
16 Correct 15 ms 23936 KB Output is correct
17 Correct 19 ms 24064 KB Output is correct
18 Correct 19 ms 24192 KB Output is correct
19 Correct 18 ms 24064 KB Output is correct
20 Correct 20 ms 24064 KB Output is correct
21 Correct 17 ms 24064 KB Output is correct
22 Correct 18 ms 24064 KB Output is correct
23 Correct 18 ms 24064 KB Output is correct
24 Correct 236 ms 40180 KB Output is correct
25 Correct 279 ms 50544 KB Output is correct
26 Correct 227 ms 40048 KB Output is correct
27 Correct 314 ms 55288 KB Output is correct
28 Correct 282 ms 41456 KB Output is correct
29 Correct 220 ms 40552 KB Output is correct
30 Correct 495 ms 43504 KB Output is correct
31 Correct 141 ms 39220 KB Output is correct
32 Correct 116 ms 30200 KB Output is correct
33 Correct 362 ms 41992 KB Output is correct
34 Correct 425 ms 45736 KB Output is correct
35 Correct 425 ms 43640 KB Output is correct
36 Correct 423 ms 43512 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 14 ms 23936 KB Output is correct
3 Correct 20 ms 23936 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 14 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 14 ms 23936 KB Output is correct
9 Correct 18 ms 23936 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 15 ms 23936 KB Output is correct
12 Correct 15 ms 23936 KB Output is correct
13 Correct 17 ms 23936 KB Output is correct
14 Correct 15 ms 23936 KB Output is correct
15 Correct 16 ms 23936 KB Output is correct
16 Correct 15 ms 23936 KB Output is correct
17 Correct 19 ms 24064 KB Output is correct
18 Correct 19 ms 24192 KB Output is correct
19 Correct 18 ms 24064 KB Output is correct
20 Correct 20 ms 24064 KB Output is correct
21 Correct 17 ms 24064 KB Output is correct
22 Correct 18 ms 24064 KB Output is correct
23 Correct 18 ms 24064 KB Output is correct
24 Correct 236 ms 40180 KB Output is correct
25 Correct 279 ms 50544 KB Output is correct
26 Correct 227 ms 40048 KB Output is correct
27 Correct 314 ms 55288 KB Output is correct
28 Correct 282 ms 41456 KB Output is correct
29 Correct 220 ms 40552 KB Output is correct
30 Correct 495 ms 43504 KB Output is correct
31 Correct 141 ms 39220 KB Output is correct
32 Correct 116 ms 30200 KB Output is correct
33 Correct 362 ms 41992 KB Output is correct
34 Correct 425 ms 45736 KB Output is correct
35 Correct 425 ms 43640 KB Output is correct
36 Correct 423 ms 43512 KB Output is correct
37 Correct 266 ms 40176 KB Output is correct
38 Correct 330 ms 55288 KB Output is correct
39 Correct 387 ms 55168 KB Output is correct
40 Correct 255 ms 45816 KB Output is correct
41 Correct 17 ms 23936 KB Output is correct
42 Correct 554 ms 43640 KB Output is correct
43 Correct 393 ms 41848 KB Output is correct
44 Correct 463 ms 45696 KB Output is correct
45 Correct 467 ms 43768 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 14 ms 23936 KB Output is correct
3 Correct 20 ms 23936 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 14 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 14 ms 23936 KB Output is correct
9 Correct 18 ms 23936 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 15 ms 23936 KB Output is correct
12 Correct 15 ms 23936 KB Output is correct
13 Correct 17 ms 23936 KB Output is correct
14 Correct 15 ms 23936 KB Output is correct
15 Correct 16 ms 23936 KB Output is correct
16 Correct 15 ms 23936 KB Output is correct
17 Correct 19 ms 24064 KB Output is correct
18 Correct 19 ms 24192 KB Output is correct
19 Correct 18 ms 24064 KB Output is correct
20 Correct 20 ms 24064 KB Output is correct
21 Correct 17 ms 24064 KB Output is correct
22 Correct 18 ms 24064 KB Output is correct
23 Correct 18 ms 24064 KB Output is correct
24 Correct 236 ms 40180 KB Output is correct
25 Correct 279 ms 50544 KB Output is correct
26 Correct 227 ms 40048 KB Output is correct
27 Correct 314 ms 55288 KB Output is correct
28 Correct 282 ms 41456 KB Output is correct
29 Correct 220 ms 40552 KB Output is correct
30 Correct 495 ms 43504 KB Output is correct
31 Correct 141 ms 39220 KB Output is correct
32 Correct 116 ms 30200 KB Output is correct
33 Correct 362 ms 41992 KB Output is correct
34 Correct 425 ms 45736 KB Output is correct
35 Correct 425 ms 43640 KB Output is correct
36 Correct 423 ms 43512 KB Output is correct
37 Correct 266 ms 40176 KB Output is correct
38 Correct 330 ms 55288 KB Output is correct
39 Correct 387 ms 55168 KB Output is correct
40 Correct 255 ms 45816 KB Output is correct
41 Correct 17 ms 23936 KB Output is correct
42 Correct 554 ms 43640 KB Output is correct
43 Correct 393 ms 41848 KB Output is correct
44 Correct 463 ms 45696 KB Output is correct
45 Correct 467 ms 43768 KB Output is correct
46 Correct 1267 ms 166996 KB Output is correct
47 Correct 1744 ms 250500 KB Output is correct
48 Correct 2036 ms 236720 KB Output is correct
49 Correct 1270 ms 189940 KB Output is correct
50 Correct 3303 ms 192000 KB Output is correct
51 Correct 2156 ms 179004 KB Output is correct
52 Correct 2864 ms 195260 KB Output is correct
53 Correct 2871 ms 160480 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 51320 KB Output is correct
2 Correct 322 ms 43128 KB Output is correct
3 Correct 239 ms 40428 KB Output is correct
4 Correct 318 ms 47608 KB Output is correct
5 Correct 16 ms 23936 KB Output is correct
6 Correct 296 ms 42024 KB Output is correct
7 Correct 138 ms 33876 KB Output is correct
8 Correct 126 ms 30200 KB Output is correct
9 Correct 256 ms 40528 KB Output is correct
10 Correct 272 ms 45896 KB Output is correct
11 Correct 189 ms 40432 KB Output is correct
12 Correct 17 ms 23936 KB Output is correct
13 Correct 14 ms 23936 KB Output is correct
14 Correct 20 ms 23936 KB Output is correct
15 Correct 15 ms 23936 KB Output is correct
16 Correct 19 ms 23936 KB Output is correct
17 Correct 14 ms 23936 KB Output is correct
18 Correct 19 ms 23936 KB Output is correct
19 Correct 14 ms 23936 KB Output is correct
20 Correct 18 ms 23936 KB Output is correct
21 Correct 15 ms 23936 KB Output is correct
22 Correct 15 ms 23936 KB Output is correct
23 Correct 15 ms 23936 KB Output is correct
24 Correct 17 ms 23936 KB Output is correct
25 Correct 15 ms 23936 KB Output is correct
26 Correct 16 ms 23936 KB Output is correct
27 Correct 15 ms 23936 KB Output is correct
28 Correct 19 ms 24064 KB Output is correct
29 Correct 19 ms 24192 KB Output is correct
30 Correct 18 ms 24064 KB Output is correct
31 Correct 20 ms 24064 KB Output is correct
32 Correct 17 ms 24064 KB Output is correct
33 Correct 18 ms 24064 KB Output is correct
34 Correct 18 ms 24064 KB Output is correct
35 Correct 236 ms 40180 KB Output is correct
36 Correct 279 ms 50544 KB Output is correct
37 Correct 227 ms 40048 KB Output is correct
38 Correct 314 ms 55288 KB Output is correct
39 Correct 282 ms 41456 KB Output is correct
40 Correct 220 ms 40552 KB Output is correct
41 Correct 495 ms 43504 KB Output is correct
42 Correct 141 ms 39220 KB Output is correct
43 Correct 116 ms 30200 KB Output is correct
44 Correct 362 ms 41992 KB Output is correct
45 Correct 425 ms 45736 KB Output is correct
46 Correct 425 ms 43640 KB Output is correct
47 Correct 423 ms 43512 KB Output is correct
48 Correct 266 ms 40176 KB Output is correct
49 Correct 330 ms 55288 KB Output is correct
50 Correct 387 ms 55168 KB Output is correct
51 Correct 255 ms 45816 KB Output is correct
52 Correct 17 ms 23936 KB Output is correct
53 Correct 554 ms 43640 KB Output is correct
54 Correct 393 ms 41848 KB Output is correct
55 Correct 463 ms 45696 KB Output is correct
56 Correct 467 ms 43768 KB Output is correct
57 Correct 329 ms 49316 KB Output is correct
58 Correct 283 ms 45816 KB Output is correct
59 Correct 284 ms 45944 KB Output is correct
60 Correct 421 ms 55160 KB Output is correct
61 Correct 414 ms 43512 KB Output is correct
62 Correct 15 ms 23936 KB Output is correct
63 Correct 549 ms 43512 KB Output is correct
64 Correct 386 ms 41720 KB Output is correct
65 Correct 435 ms 42612 KB Output is correct
66 Correct 539 ms 43640 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 51320 KB Output is correct
2 Correct 322 ms 43128 KB Output is correct
3 Correct 239 ms 40428 KB Output is correct
4 Correct 318 ms 47608 KB Output is correct
5 Correct 16 ms 23936 KB Output is correct
6 Correct 296 ms 42024 KB Output is correct
7 Correct 138 ms 33876 KB Output is correct
8 Correct 126 ms 30200 KB Output is correct
9 Correct 256 ms 40528 KB Output is correct
10 Correct 272 ms 45896 KB Output is correct
11 Correct 189 ms 40432 KB Output is correct
12 Correct 17 ms 23936 KB Output is correct
13 Correct 14 ms 23936 KB Output is correct
14 Correct 20 ms 23936 KB Output is correct
15 Correct 15 ms 23936 KB Output is correct
16 Correct 19 ms 23936 KB Output is correct
17 Correct 14 ms 23936 KB Output is correct
18 Correct 19 ms 23936 KB Output is correct
19 Correct 14 ms 23936 KB Output is correct
20 Correct 18 ms 23936 KB Output is correct
21 Correct 15 ms 23936 KB Output is correct
22 Correct 15 ms 23936 KB Output is correct
23 Correct 15 ms 23936 KB Output is correct
24 Correct 17 ms 23936 KB Output is correct
25 Correct 15 ms 23936 KB Output is correct
26 Correct 16 ms 23936 KB Output is correct
27 Correct 15 ms 23936 KB Output is correct
28 Correct 19 ms 24064 KB Output is correct
29 Correct 19 ms 24192 KB Output is correct
30 Correct 18 ms 24064 KB Output is correct
31 Correct 20 ms 24064 KB Output is correct
32 Correct 17 ms 24064 KB Output is correct
33 Correct 18 ms 24064 KB Output is correct
34 Correct 18 ms 24064 KB Output is correct
35 Correct 236 ms 40180 KB Output is correct
36 Correct 279 ms 50544 KB Output is correct
37 Correct 227 ms 40048 KB Output is correct
38 Correct 314 ms 55288 KB Output is correct
39 Correct 282 ms 41456 KB Output is correct
40 Correct 220 ms 40552 KB Output is correct
41 Correct 495 ms 43504 KB Output is correct
42 Correct 141 ms 39220 KB Output is correct
43 Correct 116 ms 30200 KB Output is correct
44 Correct 362 ms 41992 KB Output is correct
45 Correct 425 ms 45736 KB Output is correct
46 Correct 425 ms 43640 KB Output is correct
47 Correct 423 ms 43512 KB Output is correct
48 Correct 266 ms 40176 KB Output is correct
49 Correct 330 ms 55288 KB Output is correct
50 Correct 387 ms 55168 KB Output is correct
51 Correct 255 ms 45816 KB Output is correct
52 Correct 17 ms 23936 KB Output is correct
53 Correct 554 ms 43640 KB Output is correct
54 Correct 393 ms 41848 KB Output is correct
55 Correct 463 ms 45696 KB Output is correct
56 Correct 467 ms 43768 KB Output is correct
57 Correct 1267 ms 166996 KB Output is correct
58 Correct 1744 ms 250500 KB Output is correct
59 Correct 2036 ms 236720 KB Output is correct
60 Correct 1270 ms 189940 KB Output is correct
61 Correct 3303 ms 192000 KB Output is correct
62 Correct 2156 ms 179004 KB Output is correct
63 Correct 2864 ms 195260 KB Output is correct
64 Correct 2871 ms 160480 KB Output is correct
65 Correct 329 ms 49316 KB Output is correct
66 Correct 283 ms 45816 KB Output is correct
67 Correct 284 ms 45944 KB Output is correct
68 Correct 421 ms 55160 KB Output is correct
69 Correct 414 ms 43512 KB Output is correct
70 Correct 15 ms 23936 KB Output is correct
71 Correct 549 ms 43512 KB Output is correct
72 Correct 386 ms 41720 KB Output is correct
73 Correct 435 ms 42612 KB Output is correct
74 Correct 539 ms 43640 KB Output is correct
75 Correct 1756 ms 223092 KB Output is correct
76 Correct 1383 ms 205284 KB Output is correct
77 Correct 1319 ms 192504 KB Output is correct
78 Correct 2111 ms 239192 KB Output is correct
79 Correct 3560 ms 192704 KB Output is correct
80 Correct 2239 ms 178552 KB Output is correct
81 Correct 2655 ms 182704 KB Output is correct
82 Correct 3087 ms 160460 KB Output is correct
83 Correct 3245 ms 179712 KB Output is correct