oj.uz

Submission #1097767

# Submission time Handle Problem Language Result Execution time Memory
1097767 2024-10-08T08:48:28 Z thangdz2k7 Two Dishes (JOI19_dishes) C++17
74 / 100
 2886 ms 234576 KB 
// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, m;
ll a[N], b[N], s[N], t[N], p[N], q[N];
vi event[N];

const ll inf = 1e18;
ll Max[4 * N], lz[4 * N];

void update(int u, int v, ll val, bool op, int s = 1, int l = 0, int r = m){
    if (v < l || u > r) return;
    if (u <= l && r <= v){
        if (op) Max[s] += val, lz[s] += val;
        else maxl(Max[s], val);
        return;
    }

    int mid = l + r >> 1; if (!op) val -= lz[s];
    update(u, v, val, op, s << 1, l, mid);
    update(u, v, val, op, s << 1 | 1, mid + 1, r);
    Max[s] = max(Max[s << 1], Max[s << 1 | 1]) + lz[s];
}

ll get(int u, int v, int s = 1, int l = 0, int r = m){
    if (v < l || u > r) return -inf;
    if (u <= l && r <= v) return Max[s];

    int mid = l + r >> 1;
    return max(get(u, v, s << 1, l, mid), get(u, v, s << 1 | 1, mid + 1, r)) + lz[s];
}

void solve(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> a[i] >> s[i] >> p[i], a[i] += a[i - 1];
    for (int i = 1; i <= m; ++ i) cin >> b[i] >> t[i] >> q[i], b[i] += b[i - 1];

    for (int i = 1; i <= n; ++ i) s[i] = upper_bound(b, b + m + 1, s[i] - a[i]) - b - 1;
    for (int i = 1; i <= m; ++ i){
        t[i] = upper_bound(a, a + n + 1, t[i] - b[i]) - a;
        event[t[i]].pb(i);
    }

    for (int i = 1; i <= 4 * m + 4; ++ i) Max[i] = -inf, lz[i] = 0;
    update(0, 0, 0, 0);

    for (int i = 1; i <= n + 1; ++ i){
        for (int j : event[i]){
            ll f = get(0, j - 1);
            update(j, j, f, 0);
        }
        ll f = get(0, s[i]);
        update(s[i] + 1, s[i] + 1, f, 0);
        update(0, s[i], p[i], 1);
        for (int j : event[i]) update(j, m, q[j], 1);
    }
    cout << Max[1];
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message

dishes.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
dishes.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
dishes.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
dishes.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
dishes.cpp: In function 'void update(int, int, ll, bool, int, int, int)':
dishes.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int mid = l + r >> 1; if (!op) val -= lz[s];
      |               ~~^~~
dishes.cpp: In function 'll get(int, int, int, int, int)':
dishes.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = l + r >> 1;
      |               ~~^~~
dishes.cpp: In function 'int main()':
dishes.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 56708 KB Output is correct
2 Correct 296 ms 63060 KB Output is correct
3 Correct 200 ms 60108 KB Output is correct
4 Correct 244 ms 63428 KB Output is correct
5 Correct 12 ms 23896 KB Output is correct
6 Correct 265 ms 61392 KB Output is correct
7 Correct 136 ms 48896 KB Output is correct
8 Correct 59 ms 35444 KB Output is correct
9 Correct 201 ms 61108 KB Output is correct
10 Correct 259 ms 59472 KB Output is correct
11 Correct 175 ms 54576 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 10 ms 23840 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 10 ms 23956 KB Output is correct
10 Correct 12 ms 23900 KB Output is correct
11 Correct 10 ms 23992 KB Output is correct
12 Correct 11 ms 23900 KB Output is correct
13 Correct 10 ms 23896 KB Output is correct
14 Correct 11 ms 23908 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Correct 11 ms 23912 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 10 ms 23840 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 10 ms 23956 KB Output is correct
10 Correct 12 ms 23900 KB Output is correct
11 Correct 10 ms 23992 KB Output is correct
12 Correct 11 ms 23900 KB Output is correct
13 Correct 10 ms 23896 KB Output is correct
14 Correct 11 ms 23908 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Correct 11 ms 23912 KB Output is correct
17 Correct 11 ms 24156 KB Output is correct
18 Correct 11 ms 24152 KB Output is correct
19 Correct 12 ms 24156 KB Output is correct
20 Correct 12 ms 24180 KB Output is correct
21 Correct 12 ms 24152 KB Output is correct
22 Correct 13 ms 24156 KB Output is correct
23 Correct 12 ms 24120 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 10 ms 23840 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 10 ms 23956 KB Output is correct
10 Correct 12 ms 23900 KB Output is correct
11 Correct 10 ms 23992 KB Output is correct
12 Correct 11 ms 23900 KB Output is correct
13 Correct 10 ms 23896 KB Output is correct
14 Correct 11 ms 23908 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Correct 11 ms 23912 KB Output is correct
17 Correct 11 ms 24156 KB Output is correct
18 Correct 11 ms 24152 KB Output is correct
19 Correct 12 ms 24156 KB Output is correct
20 Correct 12 ms 24180 KB Output is correct
21 Correct 12 ms 24152 KB Output is correct
22 Correct 13 ms 24156 KB Output is correct
23 Correct 12 ms 24120 KB Output is correct
24 Correct 252 ms 57288 KB Output is correct
25 Correct 198 ms 57296 KB Output is correct
26 Correct 235 ms 57544 KB Output is correct
27 Correct 221 ms 62804 KB Output is correct
28 Correct 245 ms 58516 KB Output is correct
29 Correct 194 ms 58112 KB Output is correct
30 Correct 424 ms 60436 KB Output is correct
31 Correct 151 ms 47372 KB Output is correct
32 Correct 55 ms 33876 KB Output is correct
33 Correct 272 ms 58992 KB Output is correct
34 Correct 332 ms 58312 KB Output is correct
35 Correct 364 ms 54096 KB Output is correct
36 Correct 357 ms 54020 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 10 ms 23840 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 10 ms 23956 KB Output is correct
10 Correct 12 ms 23900 KB Output is correct
11 Correct 10 ms 23992 KB Output is correct
12 Correct 11 ms 23900 KB Output is correct
13 Correct 10 ms 23896 KB Output is correct
14 Correct 11 ms 23908 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Correct 11 ms 23912 KB Output is correct
17 Correct 11 ms 24156 KB Output is correct
18 Correct 11 ms 24152 KB Output is correct
19 Correct 12 ms 24156 KB Output is correct
20 Correct 12 ms 24180 KB Output is correct
21 Correct 12 ms 24152 KB Output is correct
22 Correct 13 ms 24156 KB Output is correct
23 Correct 12 ms 24120 KB Output is correct
24 Correct 252 ms 57288 KB Output is correct
25 Correct 198 ms 57296 KB Output is correct
26 Correct 235 ms 57544 KB Output is correct
27 Correct 221 ms 62804 KB Output is correct
28 Correct 245 ms 58516 KB Output is correct
29 Correct 194 ms 58112 KB Output is correct
30 Correct 424 ms 60436 KB Output is correct
31 Correct 151 ms 47372 KB Output is correct
32 Correct 55 ms 33876 KB Output is correct
33 Correct 272 ms 58992 KB Output is correct
34 Correct 332 ms 58312 KB Output is correct
35 Correct 364 ms 54096 KB Output is correct
36 Correct 357 ms 54020 KB Output is correct
37 Correct 238 ms 60292 KB Output is correct
38 Correct 228 ms 65620 KB Output is correct
39 Correct 273 ms 63352 KB Output is correct
40 Correct 275 ms 63056 KB Output is correct
41 Correct 10 ms 23896 KB Output is correct
42 Correct 411 ms 63592 KB Output is correct
43 Correct 278 ms 61752 KB Output is correct
44 Correct 350 ms 61088 KB Output is correct
45 Correct 397 ms 57168 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 10 ms 23840 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 10 ms 23956 KB Output is correct
10 Correct 12 ms 23900 KB Output is correct
11 Correct 10 ms 23992 KB Output is correct
12 Correct 11 ms 23900 KB Output is correct
13 Correct 10 ms 23896 KB Output is correct
14 Correct 11 ms 23908 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Correct 11 ms 23912 KB Output is correct
17 Correct 11 ms 24156 KB Output is correct
18 Correct 11 ms 24152 KB Output is correct
19 Correct 12 ms 24156 KB Output is correct
20 Correct 12 ms 24180 KB Output is correct
21 Correct 12 ms 24152 KB Output is correct
22 Correct 13 ms 24156 KB Output is correct
23 Correct 12 ms 24120 KB Output is correct
24 Correct 252 ms 57288 KB Output is correct
25 Correct 198 ms 57296 KB Output is correct
26 Correct 235 ms 57544 KB Output is correct
27 Correct 221 ms 62804 KB Output is correct
28 Correct 245 ms 58516 KB Output is correct
29 Correct 194 ms 58112 KB Output is correct
30 Correct 424 ms 60436 KB Output is correct
31 Correct 151 ms 47372 KB Output is correct
32 Correct 55 ms 33876 KB Output is correct
33 Correct 272 ms 58992 KB Output is correct
34 Correct 332 ms 58312 KB Output is correct
35 Correct 364 ms 54096 KB Output is correct
36 Correct 357 ms 54020 KB Output is correct
37 Correct 238 ms 60292 KB Output is correct
38 Correct 228 ms 65620 KB Output is correct
39 Correct 273 ms 63352 KB Output is correct
40 Correct 275 ms 63056 KB Output is correct
41 Correct 10 ms 23896 KB Output is correct
42 Correct 411 ms 63592 KB Output is correct
43 Correct 278 ms 61752 KB Output is correct
44 Correct 350 ms 61088 KB Output is correct
45 Correct 397 ms 57168 KB Output is correct
46 Correct 1297 ms 207500 KB Output is correct
47 Correct 1192 ms 234576 KB Output is correct
48 Correct 1463 ms 221136 KB Output is correct
49 Correct 1500 ms 221020 KB Output is correct
50 Correct 2886 ms 223056 KB Output is correct
51 Correct 1790 ms 212624 KB Output is correct
52 Correct 1927 ms 202176 KB Output is correct
53 Correct 2625 ms 191640 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 56708 KB Output is correct
2 Correct 296 ms 63060 KB Output is correct
3 Correct 200 ms 60108 KB Output is correct
4 Correct 244 ms 63428 KB Output is correct
5 Correct 12 ms 23896 KB Output is correct
6 Correct 265 ms 61392 KB Output is correct
7 Correct 136 ms 48896 KB Output is correct
8 Correct 59 ms 35444 KB Output is correct
9 Correct 201 ms 61108 KB Output is correct
10 Correct 259 ms 59472 KB Output is correct
11 Correct 175 ms 54576 KB Output is correct
12 Correct 10 ms 23900 KB Output is correct
13 Correct 10 ms 23900 KB Output is correct
14 Correct 10 ms 23900 KB Output is correct
15 Correct 11 ms 23900 KB Output is correct
16 Correct 10 ms 23900 KB Output is correct
17 Correct 10 ms 23900 KB Output is correct
18 Correct 10 ms 23840 KB Output is correct
19 Correct 11 ms 23900 KB Output is correct
20 Correct 10 ms 23956 KB Output is correct
21 Correct 12 ms 23900 KB Output is correct
22 Correct 10 ms 23992 KB Output is correct
23 Correct 11 ms 23900 KB Output is correct
24 Correct 10 ms 23896 KB Output is correct
25 Correct 11 ms 23908 KB Output is correct
26 Correct 10 ms 23900 KB Output is correct
27 Correct 11 ms 23912 KB Output is correct
28 Correct 11 ms 24156 KB Output is correct
29 Correct 11 ms 24152 KB Output is correct
30 Correct 12 ms 24156 KB Output is correct
31 Correct 12 ms 24180 KB Output is correct
32 Correct 12 ms 24152 KB Output is correct
33 Correct 13 ms 24156 KB Output is correct
34 Correct 12 ms 24120 KB Output is correct
35 Correct 252 ms 57288 KB Output is correct
36 Correct 198 ms 57296 KB Output is correct
37 Correct 235 ms 57544 KB Output is correct
38 Correct 221 ms 62804 KB Output is correct
39 Correct 245 ms 58516 KB Output is correct
40 Correct 194 ms 58112 KB Output is correct
41 Correct 424 ms 60436 KB Output is correct
42 Correct 151 ms 47372 KB Output is correct
43 Correct 55 ms 33876 KB Output is correct
44 Correct 272 ms 58992 KB Output is correct
45 Correct 332 ms 58312 KB Output is correct
46 Correct 364 ms 54096 KB Output is correct
47 Correct 357 ms 54020 KB Output is correct
48 Correct 238 ms 60292 KB Output is correct
49 Correct 228 ms 65620 KB Output is correct
50 Correct 273 ms 63352 KB Output is correct
51 Correct 275 ms 63056 KB Output is correct
52 Correct 10 ms 23896 KB Output is correct
53 Correct 411 ms 63592 KB Output is correct
54 Correct 278 ms 61752 KB Output is correct
55 Correct 350 ms 61088 KB Output is correct
56 Correct 397 ms 57168 KB Output is correct
57 Incorrect 255 ms 61024 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 56708 KB Output is correct
2 Correct 296 ms 63060 KB Output is correct
3 Correct 200 ms 60108 KB Output is correct
4 Correct 244 ms 63428 KB Output is correct
5 Correct 12 ms 23896 KB Output is correct
6 Correct 265 ms 61392 KB Output is correct
7 Correct 136 ms 48896 KB Output is correct
8 Correct 59 ms 35444 KB Output is correct
9 Correct 201 ms 61108 KB Output is correct
10 Correct 259 ms 59472 KB Output is correct
11 Correct 175 ms 54576 KB Output is correct
12 Correct 10 ms 23900 KB Output is correct
13 Correct 10 ms 23900 KB Output is correct
14 Correct 10 ms 23900 KB Output is correct
15 Correct 11 ms 23900 KB Output is correct
16 Correct 10 ms 23900 KB Output is correct
17 Correct 10 ms 23900 KB Output is correct
18 Correct 10 ms 23840 KB Output is correct
19 Correct 11 ms 23900 KB Output is correct
20 Correct 10 ms 23956 KB Output is correct
21 Correct 12 ms 23900 KB Output is correct
22 Correct 10 ms 23992 KB Output is correct
23 Correct 11 ms 23900 KB Output is correct
24 Correct 10 ms 23896 KB Output is correct
25 Correct 11 ms 23908 KB Output is correct
26 Correct 10 ms 23900 KB Output is correct
27 Correct 11 ms 23912 KB Output is correct
28 Correct 11 ms 24156 KB Output is correct
29 Correct 11 ms 24152 KB Output is correct
30 Correct 12 ms 24156 KB Output is correct
31 Correct 12 ms 24180 KB Output is correct
32 Correct 12 ms 24152 KB Output is correct
33 Correct 13 ms 24156 KB Output is correct
34 Correct 12 ms 24120 KB Output is correct
35 Correct 252 ms 57288 KB Output is correct
36 Correct 198 ms 57296 KB Output is correct
37 Correct 235 ms 57544 KB Output is correct
38 Correct 221 ms 62804 KB Output is correct
39 Correct 245 ms 58516 KB Output is correct
40 Correct 194 ms 58112 KB Output is correct
41 Correct 424 ms 60436 KB Output is correct
42 Correct 151 ms 47372 KB Output is correct
43 Correct 55 ms 33876 KB Output is correct
44 Correct 272 ms 58992 KB Output is correct
45 Correct 332 ms 58312 KB Output is correct
46 Correct 364 ms 54096 KB Output is correct
47 Correct 357 ms 54020 KB Output is correct
48 Correct 238 ms 60292 KB Output is correct
49 Correct 228 ms 65620 KB Output is correct
50 Correct 273 ms 63352 KB Output is correct
51 Correct 275 ms 63056 KB Output is correct
52 Correct 10 ms 23896 KB Output is correct
53 Correct 411 ms 63592 KB Output is correct
54 Correct 278 ms 61752 KB Output is correct
55 Correct 350 ms 61088 KB Output is correct
56 Correct 397 ms 57168 KB Output is correct
57 Correct 1297 ms 207500 KB Output is correct
58 Correct 1192 ms 234576 KB Output is correct
59 Correct 1463 ms 221136 KB Output is correct
60 Correct 1500 ms 221020 KB Output is correct
61 Correct 2886 ms 223056 KB Output is correct
62 Correct 1790 ms 212624 KB Output is correct
63 Correct 1927 ms 202176 KB Output is correct
64 Correct 2625 ms 191640 KB Output is correct
65 Incorrect 255 ms 61024 KB Output isn't correct
66 Halted 0 ms 0 KB -