oj.uz

Submission #944614

# Submission time Handle Problem Language Result Execution time Memory
944614 2024-03-13T01:53:14 Z LOLOLO Two Dishes (JOI19_dishes) C++17
74 / 100
 3328 ms 263068 KB 
#include <bits/stdc++.h>
typedef long long ll;
 
#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
 
using namespace std;
const int N = 1e6 + 10;
ll A[N], B[N], SA[N], SB[N], S[N], T[N], Q[N], P[N];
vector <pair <ll, ll>> pos[N];
struct ST{
    vector <ll> seg, laz;
    ST(int n) {
        for (int i = 0; i <= n * 4 + 100; i++) {
            seg.pb(0);
            laz.pb(0);
        }
    }
 
    void push(int id) {
        ll &t = laz[id];
        laz[id * 2] += t;
        laz[id * 2 + 1] += t;
        seg[id * 2] += t;
        seg[id * 2 + 1] += t;
        t = 0;
    }
 
    void upd(int id, int l, int r, int u, int v, ll t) {
        if (l > v || r < u)
            return;
 
        if (l >= u && r <= v) {
            laz[id] += t;
            seg[id] += t;
            return;
        }
 
        push(id);
        int m = (l + r) / 2;
        upd(id * 2, l, m, u, v, t);
        upd(id * 2 + 1, m + 1, r, u, v, t);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }
 
    void point(int id, int l, int r, int p, ll v) {
        if (l > p || r < p)
            return;
 
        if (l == r) {
            seg[id] = max(seg[id], v);
            return;
        }
 
        push(id);
        int m = (l + r) / 2;
        point(id * 2, l, m, p, v);
        point(id * 2 + 1, m + 1, r, p, v);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }
 
    ll get(int id, int l, int r, int u, int v) {
        if (u > v || l > v || r < u)
            return -1e16;
 
        if (l >= u && r <= v)
            return seg[id];
 
        push(id);
        int m = (l + r) / 2;
        return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
    }
};
 
vector <pair <ll, ll>> compress(vector < pair <ll, ll>> &v) {
    vector <pair <ll, ll>> st;
    for (auto x : v) {
        if (st.empty() || st.back().f != x.f) {
            st.pb(x);
        } else {
            st[sz(st) - 1].s += x.s;
        }
    }
    return st;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll ans = 0;
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {
        cin >> A[i] >> S[i] >> P[i];
        SA[i] = SA[i - 1] + A[i];
    }
 
    for (int i = 1; i <= m; i++) {
        cin >> B[i] >> T[i] >> Q[i];
        SB[i] = SB[i - 1] + B[i];
    }
 
    for (int i = 1; i <= n; i++) {
        if (SA[i] > S[i])
            continue;
        
        ans += P[i];
        int id = upper_bound(SB, SB + 1 + m, S[i] - SA[i]) - SB - 1;
        pos[i - 1].pb({id + 1, -P[i]});
    }
 
    for (int i = 1; i <= m; i++) {
        if (SB[i] > T[i])
            continue;
 
        int id = upper_bound(SA, SA + 1 + n, T[i] - SB[i]) - SA - 1;
        pos[id].pb({i, Q[i]});
    }
 
    for (int i = 1; i <= n; i++) {
        sort(all(pos[i]));
        pos[i] = compress(pos[i]);
    }
 
    ST seg(m + 10);
 
    int lx = 0;
    for (int i = 0; i <= n; i++) {
        ll cur = 0;
        for (auto x : pos[i]) {
            cur += x.s;
        }
 
        if (sz(pos[i])) {
            lx = pos[i].back().f;
        } else {
            lx = 0;
        }
 
        vector <pair <ll, ll>> save;
        for (int j = sz(pos[i]) - 1; j >= 0; j--) {
            ll t = seg.get(1, 0, m, 0, pos[i][j].f) + cur;
            save.pb({pos[i][j].f, t});
            seg.upd(1, 0, m, pos[i][j].f, m, pos[i][j].s);
            cur -= pos[i][j].s;
        }
 
        for (auto x : save) {
            seg.point(1, 0, m, x.f, x.s);
        }
    }
 
    cout << seg.get(1, 0, m, lx, m) + ans << '\n';
    return 0; 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 80816 KB Output is correct
2 Correct 293 ms 83724 KB Output is correct
3 Correct 239 ms 88232 KB Output is correct
4 Correct 208 ms 75940 KB Output is correct
5 Correct 7 ms 35420 KB Output is correct
6 Correct 279 ms 82024 KB Output is correct
7 Correct 158 ms 73620 KB Output is correct
8 Correct 79 ms 53072 KB Output is correct
9 Correct 237 ms 91268 KB Output is correct
10 Correct 260 ms 76836 KB Output is correct
11 Correct 203 ms 86164 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35420 KB Output is correct
2 Correct 8 ms 35532 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35416 KB Output is correct
6 Correct 7 ms 35420 KB Output is correct
7 Correct 7 ms 35416 KB Output is correct
8 Correct 7 ms 35420 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 7 ms 35420 KB Output is correct
11 Correct 7 ms 35416 KB Output is correct
12 Correct 7 ms 35540 KB Output is correct
13 Correct 8 ms 35420 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 8 ms 35500 KB Output is correct
16 Correct 8 ms 35420 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35420 KB Output is correct
2 Correct 8 ms 35532 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35416 KB Output is correct
6 Correct 7 ms 35420 KB Output is correct
7 Correct 7 ms 35416 KB Output is correct
8 Correct 7 ms 35420 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 7 ms 35420 KB Output is correct
11 Correct 7 ms 35416 KB Output is correct
12 Correct 7 ms 35540 KB Output is correct
13 Correct 8 ms 35420 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 8 ms 35500 KB Output is correct
16 Correct 8 ms 35420 KB Output is correct
17 Correct 9 ms 37976 KB Output is correct
18 Correct 9 ms 37980 KB Output is correct
19 Correct 10 ms 37980 KB Output is correct
20 Correct 10 ms 35932 KB Output is correct
21 Correct 10 ms 37980 KB Output is correct
22 Correct 10 ms 37864 KB Output is correct
23 Correct 10 ms 37980 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35420 KB Output is correct
2 Correct 8 ms 35532 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35416 KB Output is correct
6 Correct 7 ms 35420 KB Output is correct
7 Correct 7 ms 35416 KB Output is correct
8 Correct 7 ms 35420 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 7 ms 35420 KB Output is correct
11 Correct 7 ms 35416 KB Output is correct
12 Correct 7 ms 35540 KB Output is correct
13 Correct 8 ms 35420 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 8 ms 35500 KB Output is correct
16 Correct 8 ms 35420 KB Output is correct
17 Correct 9 ms 37976 KB Output is correct
18 Correct 9 ms 37980 KB Output is correct
19 Correct 10 ms 37980 KB Output is correct
20 Correct 10 ms 35932 KB Output is correct
21 Correct 10 ms 37980 KB Output is correct
22 Correct 10 ms 37864 KB Output is correct
23 Correct 10 ms 37980 KB Output is correct
24 Correct 304 ms 82072 KB Output is correct
25 Correct 212 ms 85964 KB Output is correct
26 Correct 269 ms 83508 KB Output is correct
27 Correct 236 ms 79012 KB Output is correct
28 Correct 290 ms 84184 KB Output is correct
29 Correct 236 ms 88348 KB Output is correct
30 Correct 518 ms 80516 KB Output is correct
31 Correct 169 ms 68732 KB Output is correct
32 Correct 73 ms 52052 KB Output is correct
33 Correct 282 ms 75616 KB Output is correct
34 Correct 393 ms 78872 KB Output is correct
35 Correct 454 ms 77828 KB Output is correct
36 Correct 435 ms 78204 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35420 KB Output is correct
2 Correct 8 ms 35532 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35416 KB Output is correct
6 Correct 7 ms 35420 KB Output is correct
7 Correct 7 ms 35416 KB Output is correct
8 Correct 7 ms 35420 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 7 ms 35420 KB Output is correct
11 Correct 7 ms 35416 KB Output is correct
12 Correct 7 ms 35540 KB Output is correct
13 Correct 8 ms 35420 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 8 ms 35500 KB Output is correct
16 Correct 8 ms 35420 KB Output is correct
17 Correct 9 ms 37976 KB Output is correct
18 Correct 9 ms 37980 KB Output is correct
19 Correct 10 ms 37980 KB Output is correct
20 Correct 10 ms 35932 KB Output is correct
21 Correct 10 ms 37980 KB Output is correct
22 Correct 10 ms 37864 KB Output is correct
23 Correct 10 ms 37980 KB Output is correct
24 Correct 304 ms 82072 KB Output is correct
25 Correct 212 ms 85964 KB Output is correct
26 Correct 269 ms 83508 KB Output is correct
27 Correct 236 ms 79012 KB Output is correct
28 Correct 290 ms 84184 KB Output is correct
29 Correct 236 ms 88348 KB Output is correct
30 Correct 518 ms 80516 KB Output is correct
31 Correct 169 ms 68732 KB Output is correct
32 Correct 73 ms 52052 KB Output is correct
33 Correct 282 ms 75616 KB Output is correct
34 Correct 393 ms 78872 KB Output is correct
35 Correct 454 ms 77828 KB Output is correct
36 Correct 435 ms 78204 KB Output is correct
37 Correct 309 ms 83796 KB Output is correct
38 Correct 250 ms 77912 KB Output is correct
39 Correct 241 ms 79164 KB Output is correct
40 Correct 243 ms 80580 KB Output is correct
41 Correct 7 ms 35416 KB Output is correct
42 Correct 493 ms 82988 KB Output is correct
43 Correct 326 ms 78524 KB Output is correct
44 Correct 443 ms 82292 KB Output is correct
45 Correct 464 ms 81416 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35420 KB Output is correct
2 Correct 8 ms 35532 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35416 KB Output is correct
6 Correct 7 ms 35420 KB Output is correct
7 Correct 7 ms 35416 KB Output is correct
8 Correct 7 ms 35420 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 7 ms 35420 KB Output is correct
11 Correct 7 ms 35416 KB Output is correct
12 Correct 7 ms 35540 KB Output is correct
13 Correct 8 ms 35420 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 8 ms 35500 KB Output is correct
16 Correct 8 ms 35420 KB Output is correct
17 Correct 9 ms 37976 KB Output is correct
18 Correct 9 ms 37980 KB Output is correct
19 Correct 10 ms 37980 KB Output is correct
20 Correct 10 ms 35932 KB Output is correct
21 Correct 10 ms 37980 KB Output is correct
22 Correct 10 ms 37864 KB Output is correct
23 Correct 10 ms 37980 KB Output is correct
24 Correct 304 ms 82072 KB Output is correct
25 Correct 212 ms 85964 KB Output is correct
26 Correct 269 ms 83508 KB Output is correct
27 Correct 236 ms 79012 KB Output is correct
28 Correct 290 ms 84184 KB Output is correct
29 Correct 236 ms 88348 KB Output is correct
30 Correct 518 ms 80516 KB Output is correct
31 Correct 169 ms 68732 KB Output is correct
32 Correct 73 ms 52052 KB Output is correct
33 Correct 282 ms 75616 KB Output is correct
34 Correct 393 ms 78872 KB Output is correct
35 Correct 454 ms 77828 KB Output is correct
36 Correct 435 ms 78204 KB Output is correct
37 Correct 309 ms 83796 KB Output is correct
38 Correct 250 ms 77912 KB Output is correct
39 Correct 241 ms 79164 KB Output is correct
40 Correct 243 ms 80580 KB Output is correct
41 Correct 7 ms 35416 KB Output is correct
42 Correct 493 ms 82988 KB Output is correct
43 Correct 326 ms 78524 KB Output is correct
44 Correct 443 ms 82292 KB Output is correct
45 Correct 464 ms 81416 KB Output is correct
46 Correct 1521 ms 239976 KB Output is correct
47 Correct 1272 ms 244536 KB Output is correct
48 Correct 1241 ms 239248 KB Output is correct
49 Correct 1241 ms 239636 KB Output is correct
50 Correct 3328 ms 263068 KB Output is correct
51 Correct 1817 ms 230536 KB Output is correct
52 Correct 2445 ms 250044 KB Output is correct
53 Correct 3032 ms 229988 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 80816 KB Output is correct
2 Correct 293 ms 83724 KB Output is correct
3 Correct 239 ms 88232 KB Output is correct
4 Correct 208 ms 75940 KB Output is correct
5 Correct 7 ms 35420 KB Output is correct
6 Correct 279 ms 82024 KB Output is correct
7 Correct 158 ms 73620 KB Output is correct
8 Correct 79 ms 53072 KB Output is correct
9 Correct 237 ms 91268 KB Output is correct
10 Correct 260 ms 76836 KB Output is correct
11 Correct 203 ms 86164 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 8 ms 35532 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 7 ms 35420 KB Output is correct
16 Correct 7 ms 35416 KB Output is correct
17 Correct 7 ms 35420 KB Output is correct
18 Correct 7 ms 35416 KB Output is correct
19 Correct 7 ms 35420 KB Output is correct
20 Correct 7 ms 35420 KB Output is correct
21 Correct 7 ms 35420 KB Output is correct
22 Correct 7 ms 35416 KB Output is correct
23 Correct 7 ms 35540 KB Output is correct
24 Correct 8 ms 35420 KB Output is correct
25 Correct 7 ms 35420 KB Output is correct
26 Correct 8 ms 35500 KB Output is correct
27 Correct 8 ms 35420 KB Output is correct
28 Correct 9 ms 37976 KB Output is correct
29 Correct 9 ms 37980 KB Output is correct
30 Correct 10 ms 37980 KB Output is correct
31 Correct 10 ms 35932 KB Output is correct
32 Correct 10 ms 37980 KB Output is correct
33 Correct 10 ms 37864 KB Output is correct
34 Correct 10 ms 37980 KB Output is correct
35 Correct 304 ms 82072 KB Output is correct
36 Correct 212 ms 85964 KB Output is correct
37 Correct 269 ms 83508 KB Output is correct
38 Correct 236 ms 79012 KB Output is correct
39 Correct 290 ms 84184 KB Output is correct
40 Correct 236 ms 88348 KB Output is correct
41 Correct 518 ms 80516 KB Output is correct
42 Correct 169 ms 68732 KB Output is correct
43 Correct 73 ms 52052 KB Output is correct
44 Correct 282 ms 75616 KB Output is correct
45 Correct 393 ms 78872 KB Output is correct
46 Correct 454 ms 77828 KB Output is correct
47 Correct 435 ms 78204 KB Output is correct
48 Correct 309 ms 83796 KB Output is correct
49 Correct 250 ms 77912 KB Output is correct
50 Correct 241 ms 79164 KB Output is correct
51 Correct 243 ms 80580 KB Output is correct
52 Correct 7 ms 35416 KB Output is correct
53 Correct 493 ms 82988 KB Output is correct
54 Correct 326 ms 78524 KB Output is correct
55 Correct 443 ms 82292 KB Output is correct
56 Correct 464 ms 81416 KB Output is correct
57 Correct 285 ms 83196 KB Output is correct
58 Correct 249 ms 85904 KB Output is correct
59 Incorrect 249 ms 84380 KB Output isn't correct
60 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 80816 KB Output is correct
2 Correct 293 ms 83724 KB Output is correct
3 Correct 239 ms 88232 KB Output is correct
4 Correct 208 ms 75940 KB Output is correct
5 Correct 7 ms 35420 KB Output is correct
6 Correct 279 ms 82024 KB Output is correct
7 Correct 158 ms 73620 KB Output is correct
8 Correct 79 ms 53072 KB Output is correct
9 Correct 237 ms 91268 KB Output is correct
10 Correct 260 ms 76836 KB Output is correct
11 Correct 203 ms 86164 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 8 ms 35532 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 7 ms 35420 KB Output is correct
16 Correct 7 ms 35416 KB Output is correct
17 Correct 7 ms 35420 KB Output is correct
18 Correct 7 ms 35416 KB Output is correct
19 Correct 7 ms 35420 KB Output is correct
20 Correct 7 ms 35420 KB Output is correct
21 Correct 7 ms 35420 KB Output is correct
22 Correct 7 ms 35416 KB Output is correct
23 Correct 7 ms 35540 KB Output is correct
24 Correct 8 ms 35420 KB Output is correct
25 Correct 7 ms 35420 KB Output is correct
26 Correct 8 ms 35500 KB Output is correct
27 Correct 8 ms 35420 KB Output is correct
28 Correct 9 ms 37976 KB Output is correct
29 Correct 9 ms 37980 KB Output is correct
30 Correct 10 ms 37980 KB Output is correct
31 Correct 10 ms 35932 KB Output is correct
32 Correct 10 ms 37980 KB Output is correct
33 Correct 10 ms 37864 KB Output is correct
34 Correct 10 ms 37980 KB Output is correct
35 Correct 304 ms 82072 KB Output is correct
36 Correct 212 ms 85964 KB Output is correct
37 Correct 269 ms 83508 KB Output is correct
38 Correct 236 ms 79012 KB Output is correct
39 Correct 290 ms 84184 KB Output is correct
40 Correct 236 ms 88348 KB Output is correct
41 Correct 518 ms 80516 KB Output is correct
42 Correct 169 ms 68732 KB Output is correct
43 Correct 73 ms 52052 KB Output is correct
44 Correct 282 ms 75616 KB Output is correct
45 Correct 393 ms 78872 KB Output is correct
46 Correct 454 ms 77828 KB Output is correct
47 Correct 435 ms 78204 KB Output is correct
48 Correct 309 ms 83796 KB Output is correct
49 Correct 250 ms 77912 KB Output is correct
50 Correct 241 ms 79164 KB Output is correct
51 Correct 243 ms 80580 KB Output is correct
52 Correct 7 ms 35416 KB Output is correct
53 Correct 493 ms 82988 KB Output is correct
54 Correct 326 ms 78524 KB Output is correct
55 Correct 443 ms 82292 KB Output is correct
56 Correct 464 ms 81416 KB Output is correct
57 Correct 1521 ms 239976 KB Output is correct
58 Correct 1272 ms 244536 KB Output is correct
59 Correct 1241 ms 239248 KB Output is correct
60 Correct 1241 ms 239636 KB Output is correct
61 Correct 3328 ms 263068 KB Output is correct
62 Correct 1817 ms 230536 KB Output is correct
63 Correct 2445 ms 250044 KB Output is correct
64 Correct 3032 ms 229988 KB Output is correct
65 Correct 285 ms 83196 KB Output is correct
66 Correct 249 ms 85904 KB Output is correct
67 Incorrect 249 ms 84380 KB Output isn't correct
68 Halted 0 ms 0 KB -