oj.uz

Submission #769032

# Submission time Handle Problem Language Result Execution time Memory
769032 2023-06-29T05:21:58 Z nguyentunglam Two Dishes (JOI19_dishes) C++17
74 / 100
 3599 ms 150160 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define int long long
using namespace std;
const int N = 1e6 + 10;
long long a[N], b[N], s[N], t[N], p[N], q[N];
vector<int> event[N];
int n, m;
long long T[N << 2], lazy[N << 2];
void push(int s, int l, int r) {
    if (lazy[s] == 0) return;
    T[s] += lazy[s];
    if (l != r) {
        lazy[s << 1] += lazy[s];
        lazy[s << 1 | 1] += lazy[s];
    }
    lazy[s] = 0;
}

void up(int s, int l, int r, int from, int to, long long val, bool type) {
    push(s, l, r);
    if (l > to || r < from) return;
    if (from <= l && r <= to) {
        if (type) {
            T[s] = max(T[s], val);
        }
        else {
            lazy[s] += val;
            push(s, l, r);
        }
        return;
    }
    int mid = l + r >> 1;
    up(s << 1, l, mid, from, to, val, type);
    up(s << 1 | 1, mid + 1, r, from, to, val, type);
    T[s] = max(T[s << 1], T[s << 1 | 1]);
}

long long get(int s, int l, int r, int from, int to) {
    push(s, l, r);
    if (l > to || r < from) return -1e18;
    if (from <= l && r <= to) return T[s];
    int mid = l + r >> 1;
    return max(get(s << 1, l, mid, from, to), get(s << 1 | 1, mid + 1, r, from, to));
}


main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> s[i] >> p[i];
        p[i] = p[i];
        a[i] += a[i - 1];
    }
    for(int i = 1; i <= m; i++) {
        cin >> b[i] >> t[i] >> q[i];
        q[i] = q[i];
        b[i] += b[i - 1];
    }
    for(int i = 1; i <= n; i++) {
        int l = 0, r = m, last = -1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (a[i] + b[mid] <= s[i]) {
                last = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        s[i] = last;
    }
    for(int i = 1; i <= m; i++) {
        int l = 0, r = n, last = -1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (b[i] + a[mid] <= t[i]) {
                last = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        t[i] = last;
        if (last >= 0) {
            event[last].push_back(i);
        }
    }
    for(int i = 1; i <= 4 * (m + 1); i++) T[i] = -1e18;
    up(1, 0, m, 0, 0, 0, 1);

    for(int i = 1; i <= n + 1; i++) {
        for(int &j : event[i - 1]) {
            long long f = get(1, 0, m, 0, j - 1);
            up(1, 0, m, j, j, f, 1);
        }
        long long f = get(1, 0, m, 0, s[i]);
        up(1, 0, m, s[i] + 1, s[i] + 1, f, 1);

        up(1, 0, m, 0, s[i], p[i], 0);
        for(int &j : event[i - 1]) {
            up(1, 0, m, j, m, q[j], 0);
        }
    }
    cout << get(1, 0, m, 1, m);
}

Compilation message

dishes.cpp: In function 'void up(long long int, long long int, long long int, long long int, long long int, long long int, bool)':
dishes.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int mid = l + r >> 1;
      |               ~~^~~
dishes.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
dishes.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = l + r >> 1;
      |               ~~^~~
dishes.cpp: At global scope:
dishes.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main() {
      | ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:76:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |             int mid = l + r >> 1;
      |                       ~~^~~
dishes.cpp:88:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |             int mid = l + r >> 1;
      |                       ~~^~~
dishes.cpp:55:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:56:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:59:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:60:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 48348 KB Output is correct
2 Correct 362 ms 48336 KB Output is correct
3 Correct 250 ms 46156 KB Output is correct
4 Correct 322 ms 46988 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 325 ms 47752 KB Output is correct
7 Correct 173 ms 41444 KB Output is correct
8 Correct 66 ms 29952 KB Output is correct
9 Correct 253 ms 46616 KB Output is correct
10 Correct 359 ms 50716 KB Output is correct
11 Correct 228 ms 46200 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 12 ms 23820 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 15 ms 23944 KB Output is correct
5 Correct 12 ms 23804 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 13 ms 23856 KB Output is correct
8 Correct 12 ms 23876 KB Output is correct
9 Correct 11 ms 23764 KB Output is correct
10 Correct 11 ms 23752 KB Output is correct
11 Correct 11 ms 23816 KB Output is correct
12 Correct 11 ms 23820 KB Output is correct
13 Correct 11 ms 23784 KB Output is correct
14 Correct 11 ms 23820 KB Output is correct
15 Correct 13 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 12 ms 23820 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 15 ms 23944 KB Output is correct
5 Correct 12 ms 23804 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 13 ms 23856 KB Output is correct
8 Correct 12 ms 23876 KB Output is correct
9 Correct 11 ms 23764 KB Output is correct
10 Correct 11 ms 23752 KB Output is correct
11 Correct 11 ms 23816 KB Output is correct
12 Correct 11 ms 23820 KB Output is correct
13 Correct 11 ms 23784 KB Output is correct
14 Correct 11 ms 23820 KB Output is correct
15 Correct 13 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 14 ms 24148 KB Output is correct
18 Correct 12 ms 24196 KB Output is correct
19 Correct 14 ms 24148 KB Output is correct
20 Correct 13 ms 24092 KB Output is correct
21 Correct 15 ms 24084 KB Output is correct
22 Correct 15 ms 24028 KB Output is correct
23 Correct 14 ms 24092 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 12 ms 23820 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 15 ms 23944 KB Output is correct
5 Correct 12 ms 23804 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 13 ms 23856 KB Output is correct
8 Correct 12 ms 23876 KB Output is correct
9 Correct 11 ms 23764 KB Output is correct
10 Correct 11 ms 23752 KB Output is correct
11 Correct 11 ms 23816 KB Output is correct
12 Correct 11 ms 23820 KB Output is correct
13 Correct 11 ms 23784 KB Output is correct
14 Correct 11 ms 23820 KB Output is correct
15 Correct 13 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 14 ms 24148 KB Output is correct
18 Correct 12 ms 24196 KB Output is correct
19 Correct 14 ms 24148 KB Output is correct
20 Correct 13 ms 24092 KB Output is correct
21 Correct 15 ms 24084 KB Output is correct
22 Correct 15 ms 24028 KB Output is correct
23 Correct 14 ms 24092 KB Output is correct
24 Correct 273 ms 45564 KB Output is correct
25 Correct 244 ms 46656 KB Output is correct
26 Correct 291 ms 45916 KB Output is correct
27 Correct 265 ms 51228 KB Output is correct
28 Correct 293 ms 47328 KB Output is correct
29 Correct 228 ms 46656 KB Output is correct
30 Correct 483 ms 49252 KB Output is correct
31 Correct 176 ms 41956 KB Output is correct
32 Correct 63 ms 29908 KB Output is correct
33 Correct 330 ms 47272 KB Output is correct
34 Correct 410 ms 47724 KB Output is correct
35 Correct 459 ms 49208 KB Output is correct
36 Correct 471 ms 49048 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 12 ms 23820 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 15 ms 23944 KB Output is correct
5 Correct 12 ms 23804 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 13 ms 23856 KB Output is correct
8 Correct 12 ms 23876 KB Output is correct
9 Correct 11 ms 23764 KB Output is correct
10 Correct 11 ms 23752 KB Output is correct
11 Correct 11 ms 23816 KB Output is correct
12 Correct 11 ms 23820 KB Output is correct
13 Correct 11 ms 23784 KB Output is correct
14 Correct 11 ms 23820 KB Output is correct
15 Correct 13 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 14 ms 24148 KB Output is correct
18 Correct 12 ms 24196 KB Output is correct
19 Correct 14 ms 24148 KB Output is correct
20 Correct 13 ms 24092 KB Output is correct
21 Correct 15 ms 24084 KB Output is correct
22 Correct 15 ms 24028 KB Output is correct
23 Correct 14 ms 24092 KB Output is correct
24 Correct 273 ms 45564 KB Output is correct
25 Correct 244 ms 46656 KB Output is correct
26 Correct 291 ms 45916 KB Output is correct
27 Correct 265 ms 51228 KB Output is correct
28 Correct 293 ms 47328 KB Output is correct
29 Correct 228 ms 46656 KB Output is correct
30 Correct 483 ms 49252 KB Output is correct
31 Correct 176 ms 41956 KB Output is correct
32 Correct 63 ms 29908 KB Output is correct
33 Correct 330 ms 47272 KB Output is correct
34 Correct 410 ms 47724 KB Output is correct
35 Correct 459 ms 49208 KB Output is correct
36 Correct 471 ms 49048 KB Output is correct
37 Correct 317 ms 45924 KB Output is correct
38 Correct 279 ms 51104 KB Output is correct
39 Correct 364 ms 50732 KB Output is correct
40 Correct 357 ms 50580 KB Output is correct
41 Correct 12 ms 23764 KB Output is correct
42 Correct 516 ms 48592 KB Output is correct
43 Correct 354 ms 47212 KB Output is correct
44 Correct 425 ms 47524 KB Output is correct
45 Correct 467 ms 48968 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 12 ms 23820 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 15 ms 23944 KB Output is correct
5 Correct 12 ms 23804 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 13 ms 23856 KB Output is correct
8 Correct 12 ms 23876 KB Output is correct
9 Correct 11 ms 23764 KB Output is correct
10 Correct 11 ms 23752 KB Output is correct
11 Correct 11 ms 23816 KB Output is correct
12 Correct 11 ms 23820 KB Output is correct
13 Correct 11 ms 23784 KB Output is correct
14 Correct 11 ms 23820 KB Output is correct
15 Correct 13 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 14 ms 24148 KB Output is correct
18 Correct 12 ms 24196 KB Output is correct
19 Correct 14 ms 24148 KB Output is correct
20 Correct 13 ms 24092 KB Output is correct
21 Correct 15 ms 24084 KB Output is correct
22 Correct 15 ms 24028 KB Output is correct
23 Correct 14 ms 24092 KB Output is correct
24 Correct 273 ms 45564 KB Output is correct
25 Correct 244 ms 46656 KB Output is correct
26 Correct 291 ms 45916 KB Output is correct
27 Correct 265 ms 51228 KB Output is correct
28 Correct 293 ms 47328 KB Output is correct
29 Correct 228 ms 46656 KB Output is correct
30 Correct 483 ms 49252 KB Output is correct
31 Correct 176 ms 41956 KB Output is correct
32 Correct 63 ms 29908 KB Output is correct
33 Correct 330 ms 47272 KB Output is correct
34 Correct 410 ms 47724 KB Output is correct
35 Correct 459 ms 49208 KB Output is correct
36 Correct 471 ms 49048 KB Output is correct
37 Correct 317 ms 45924 KB Output is correct
38 Correct 279 ms 51104 KB Output is correct
39 Correct 364 ms 50732 KB Output is correct
40 Correct 357 ms 50580 KB Output is correct
41 Correct 12 ms 23764 KB Output is correct
42 Correct 516 ms 48592 KB Output is correct
43 Correct 354 ms 47212 KB Output is correct
44 Correct 425 ms 47524 KB Output is correct
45 Correct 467 ms 48968 KB Output is correct
46 Correct 1612 ms 123224 KB Output is correct
47 Correct 1440 ms 150160 KB Output is correct
48 Correct 1941 ms 150112 KB Output is correct
49 Correct 2005 ms 149776 KB Output is correct
50 Correct 3599 ms 140040 KB Output is correct
51 Correct 2162 ms 129552 KB Output is correct
52 Correct 2616 ms 127776 KB Output is correct
53 Correct 3283 ms 139628 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 48348 KB Output is correct
2 Correct 362 ms 48336 KB Output is correct
3 Correct 250 ms 46156 KB Output is correct
4 Correct 322 ms 46988 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 325 ms 47752 KB Output is correct
7 Correct 173 ms 41444 KB Output is correct
8 Correct 66 ms 29952 KB Output is correct
9 Correct 253 ms 46616 KB Output is correct
10 Correct 359 ms 50716 KB Output is correct
11 Correct 228 ms 46200 KB Output is correct
12 Correct 14 ms 23764 KB Output is correct
13 Correct 12 ms 23820 KB Output is correct
14 Correct 12 ms 23824 KB Output is correct
15 Correct 15 ms 23944 KB Output is correct
16 Correct 12 ms 23804 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 13 ms 23856 KB Output is correct
19 Correct 12 ms 23876 KB Output is correct
20 Correct 11 ms 23764 KB Output is correct
21 Correct 11 ms 23752 KB Output is correct
22 Correct 11 ms 23816 KB Output is correct
23 Correct 11 ms 23820 KB Output is correct
24 Correct 11 ms 23784 KB Output is correct
25 Correct 11 ms 23820 KB Output is correct
26 Correct 13 ms 23764 KB Output is correct
27 Correct 12 ms 23764 KB Output is correct
28 Correct 14 ms 24148 KB Output is correct
29 Correct 12 ms 24196 KB Output is correct
30 Correct 14 ms 24148 KB Output is correct
31 Correct 13 ms 24092 KB Output is correct
32 Correct 15 ms 24084 KB Output is correct
33 Correct 15 ms 24028 KB Output is correct
34 Correct 14 ms 24092 KB Output is correct
35 Correct 273 ms 45564 KB Output is correct
36 Correct 244 ms 46656 KB Output is correct
37 Correct 291 ms 45916 KB Output is correct
38 Correct 265 ms 51228 KB Output is correct
39 Correct 293 ms 47328 KB Output is correct
40 Correct 228 ms 46656 KB Output is correct
41 Correct 483 ms 49252 KB Output is correct
42 Correct 176 ms 41956 KB Output is correct
43 Correct 63 ms 29908 KB Output is correct
44 Correct 330 ms 47272 KB Output is correct
45 Correct 410 ms 47724 KB Output is correct
46 Correct 459 ms 49208 KB Output is correct
47 Correct 471 ms 49048 KB Output is correct
48 Correct 317 ms 45924 KB Output is correct
49 Correct 279 ms 51104 KB Output is correct
50 Correct 364 ms 50732 KB Output is correct
51 Correct 357 ms 50580 KB Output is correct
52 Correct 12 ms 23764 KB Output is correct
53 Correct 516 ms 48592 KB Output is correct
54 Correct 354 ms 47212 KB Output is correct
55 Correct 425 ms 47524 KB Output is correct
56 Correct 467 ms 48968 KB Output is correct
57 Incorrect 312 ms 45136 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 48348 KB Output is correct
2 Correct 362 ms 48336 KB Output is correct
3 Correct 250 ms 46156 KB Output is correct
4 Correct 322 ms 46988 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 325 ms 47752 KB Output is correct
7 Correct 173 ms 41444 KB Output is correct
8 Correct 66 ms 29952 KB Output is correct
9 Correct 253 ms 46616 KB Output is correct
10 Correct 359 ms 50716 KB Output is correct
11 Correct 228 ms 46200 KB Output is correct
12 Correct 14 ms 23764 KB Output is correct
13 Correct 12 ms 23820 KB Output is correct
14 Correct 12 ms 23824 KB Output is correct
15 Correct 15 ms 23944 KB Output is correct
16 Correct 12 ms 23804 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 13 ms 23856 KB Output is correct
19 Correct 12 ms 23876 KB Output is correct
20 Correct 11 ms 23764 KB Output is correct
21 Correct 11 ms 23752 KB Output is correct
22 Correct 11 ms 23816 KB Output is correct
23 Correct 11 ms 23820 KB Output is correct
24 Correct 11 ms 23784 KB Output is correct
25 Correct 11 ms 23820 KB Output is correct
26 Correct 13 ms 23764 KB Output is correct
27 Correct 12 ms 23764 KB Output is correct
28 Correct 14 ms 24148 KB Output is correct
29 Correct 12 ms 24196 KB Output is correct
30 Correct 14 ms 24148 KB Output is correct
31 Correct 13 ms 24092 KB Output is correct
32 Correct 15 ms 24084 KB Output is correct
33 Correct 15 ms 24028 KB Output is correct
34 Correct 14 ms 24092 KB Output is correct
35 Correct 273 ms 45564 KB Output is correct
36 Correct 244 ms 46656 KB Output is correct
37 Correct 291 ms 45916 KB Output is correct
38 Correct 265 ms 51228 KB Output is correct
39 Correct 293 ms 47328 KB Output is correct
40 Correct 228 ms 46656 KB Output is correct
41 Correct 483 ms 49252 KB Output is correct
42 Correct 176 ms 41956 KB Output is correct
43 Correct 63 ms 29908 KB Output is correct
44 Correct 330 ms 47272 KB Output is correct
45 Correct 410 ms 47724 KB Output is correct
46 Correct 459 ms 49208 KB Output is correct
47 Correct 471 ms 49048 KB Output is correct
48 Correct 317 ms 45924 KB Output is correct
49 Correct 279 ms 51104 KB Output is correct
50 Correct 364 ms 50732 KB Output is correct
51 Correct 357 ms 50580 KB Output is correct
52 Correct 12 ms 23764 KB Output is correct
53 Correct 516 ms 48592 KB Output is correct
54 Correct 354 ms 47212 KB Output is correct
55 Correct 425 ms 47524 KB Output is correct
56 Correct 467 ms 48968 KB Output is correct
57 Correct 1612 ms 123224 KB Output is correct
58 Correct 1440 ms 150160 KB Output is correct
59 Correct 1941 ms 150112 KB Output is correct
60 Correct 2005 ms 149776 KB Output is correct
61 Correct 3599 ms 140040 KB Output is correct
62 Correct 2162 ms 129552 KB Output is correct
63 Correct 2616 ms 127776 KB Output is correct
64 Correct 3283 ms 139628 KB Output is correct
65 Incorrect 312 ms 45136 KB Output isn't correct
66 Halted 0 ms 0 KB -