oj.uz

Submission #769043

# Submission time Handle Problem Language Result Execution time Memory
769043 2023-06-29T05:33:32 Z nguyentunglam Two Dishes (JOI19_dishes) C++17
100 / 100
 3690 ms 209788 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);
        }
        if (i > n) {
            up(1, 0, m, m, m, get(1, 0, m, 0, m - 1), 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, m, 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 376 ms 47132 KB Output is correct
2 Correct 411 ms 47444 KB Output is correct
3 Correct 249 ms 45316 KB Output is correct
4 Correct 346 ms 45572 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 359 ms 46344 KB Output is correct
7 Correct 169 ms 40024 KB Output is correct
8 Correct 66 ms 28448 KB Output is correct
9 Correct 242 ms 45248 KB Output is correct
10 Correct 392 ms 49876 KB Output is correct
11 Correct 227 ms 45256 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23816 KB Output is correct
4 Correct 12 ms 23840 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 15 ms 23816 KB Output is correct
8 Correct 12 ms 23844 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23768 KB Output is correct
11 Correct 11 ms 23860 KB Output is correct
12 Correct 11 ms 23848 KB Output is correct
13 Correct 14 ms 23764 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23816 KB Output is correct
4 Correct 12 ms 23840 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 15 ms 23816 KB Output is correct
8 Correct 12 ms 23844 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23768 KB Output is correct
11 Correct 11 ms 23860 KB Output is correct
12 Correct 11 ms 23848 KB Output is correct
13 Correct 14 ms 23764 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 14 ms 24020 KB Output is correct
18 Correct 16 ms 24076 KB Output is correct
19 Correct 20 ms 24020 KB Output is correct
20 Correct 16 ms 24020 KB Output is correct
21 Correct 19 ms 24092 KB Output is correct
22 Correct 15 ms 24060 KB Output is correct
23 Correct 20 ms 24004 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23816 KB Output is correct
4 Correct 12 ms 23840 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 15 ms 23816 KB Output is correct
8 Correct 12 ms 23844 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23768 KB Output is correct
11 Correct 11 ms 23860 KB Output is correct
12 Correct 11 ms 23848 KB Output is correct
13 Correct 14 ms 23764 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 14 ms 24020 KB Output is correct
18 Correct 16 ms 24076 KB Output is correct
19 Correct 20 ms 24020 KB Output is correct
20 Correct 16 ms 24020 KB Output is correct
21 Correct 19 ms 24092 KB Output is correct
22 Correct 15 ms 24060 KB Output is correct
23 Correct 20 ms 24004 KB Output is correct
24 Correct 272 ms 44416 KB Output is correct
25 Correct 278 ms 45280 KB Output is correct
26 Correct 297 ms 44488 KB Output is correct
27 Correct 272 ms 49836 KB Output is correct
28 Correct 299 ms 45956 KB Output is correct
29 Correct 223 ms 45244 KB Output is correct
30 Correct 556 ms 47792 KB Output is correct
31 Correct 208 ms 40940 KB Output is correct
32 Correct 68 ms 28916 KB Output is correct
33 Correct 387 ms 46352 KB Output is correct
34 Correct 456 ms 46664 KB Output is correct
35 Correct 569 ms 48180 KB Output is correct
36 Correct 519 ms 48112 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23816 KB Output is correct
4 Correct 12 ms 23840 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 15 ms 23816 KB Output is correct
8 Correct 12 ms 23844 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23768 KB Output is correct
11 Correct 11 ms 23860 KB Output is correct
12 Correct 11 ms 23848 KB Output is correct
13 Correct 14 ms 23764 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 14 ms 24020 KB Output is correct
18 Correct 16 ms 24076 KB Output is correct
19 Correct 20 ms 24020 KB Output is correct
20 Correct 16 ms 24020 KB Output is correct
21 Correct 19 ms 24092 KB Output is correct
22 Correct 15 ms 24060 KB Output is correct
23 Correct 20 ms 24004 KB Output is correct
24 Correct 272 ms 44416 KB Output is correct
25 Correct 278 ms 45280 KB Output is correct
26 Correct 297 ms 44488 KB Output is correct
27 Correct 272 ms 49836 KB Output is correct
28 Correct 299 ms 45956 KB Output is correct
29 Correct 223 ms 45244 KB Output is correct
30 Correct 556 ms 47792 KB Output is correct
31 Correct 208 ms 40940 KB Output is correct
32 Correct 68 ms 28916 KB Output is correct
33 Correct 387 ms 46352 KB Output is correct
34 Correct 456 ms 46664 KB Output is correct
35 Correct 569 ms 48180 KB Output is correct
36 Correct 519 ms 48112 KB Output is correct
37 Correct 344 ms 44848 KB Output is correct
38 Correct 293 ms 50256 KB Output is correct
39 Correct 491 ms 50188 KB Output is correct
40 Correct 433 ms 50232 KB Output is correct
41 Correct 14 ms 23824 KB Output is correct
42 Correct 592 ms 48148 KB Output is correct
43 Correct 529 ms 46320 KB Output is correct
44 Correct 541 ms 46760 KB Output is correct
45 Correct 542 ms 48588 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23816 KB Output is correct
4 Correct 12 ms 23840 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 15 ms 23816 KB Output is correct
8 Correct 12 ms 23844 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23768 KB Output is correct
11 Correct 11 ms 23860 KB Output is correct
12 Correct 11 ms 23848 KB Output is correct
13 Correct 14 ms 23764 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 14 ms 24020 KB Output is correct
18 Correct 16 ms 24076 KB Output is correct
19 Correct 20 ms 24020 KB Output is correct
20 Correct 16 ms 24020 KB Output is correct
21 Correct 19 ms 24092 KB Output is correct
22 Correct 15 ms 24060 KB Output is correct
23 Correct 20 ms 24004 KB Output is correct
24 Correct 272 ms 44416 KB Output is correct
25 Correct 278 ms 45280 KB Output is correct
26 Correct 297 ms 44488 KB Output is correct
27 Correct 272 ms 49836 KB Output is correct
28 Correct 299 ms 45956 KB Output is correct
29 Correct 223 ms 45244 KB Output is correct
30 Correct 556 ms 47792 KB Output is correct
31 Correct 208 ms 40940 KB Output is correct
32 Correct 68 ms 28916 KB Output is correct
33 Correct 387 ms 46352 KB Output is correct
34 Correct 456 ms 46664 KB Output is correct
35 Correct 569 ms 48180 KB Output is correct
36 Correct 519 ms 48112 KB Output is correct
37 Correct 344 ms 44848 KB Output is correct
38 Correct 293 ms 50256 KB Output is correct
39 Correct 491 ms 50188 KB Output is correct
40 Correct 433 ms 50232 KB Output is correct
41 Correct 14 ms 23824 KB Output is correct
42 Correct 592 ms 48148 KB Output is correct
43 Correct 529 ms 46320 KB Output is correct
44 Correct 541 ms 46760 KB Output is correct
45 Correct 542 ms 48588 KB Output is correct
46 Correct 1767 ms 123200 KB Output is correct
47 Correct 1515 ms 150472 KB Output is correct
48 Correct 2087 ms 150360 KB Output is correct
49 Correct 2009 ms 149836 KB Output is correct
50 Correct 3690 ms 139880 KB Output is correct
51 Correct 2353 ms 129348 KB Output is correct
52 Correct 2887 ms 127476 KB Output is correct
53 Correct 3549 ms 139236 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 47132 KB Output is correct
2 Correct 411 ms 47444 KB Output is correct
3 Correct 249 ms 45316 KB Output is correct
4 Correct 346 ms 45572 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 359 ms 46344 KB Output is correct
7 Correct 169 ms 40024 KB Output is correct
8 Correct 66 ms 28448 KB Output is correct
9 Correct 242 ms 45248 KB Output is correct
10 Correct 392 ms 49876 KB Output is correct
11 Correct 227 ms 45256 KB Output is correct
12 Correct 15 ms 23808 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 12 ms 23816 KB Output is correct
15 Correct 12 ms 23840 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 15 ms 23816 KB Output is correct
19 Correct 12 ms 23844 KB Output is correct
20 Correct 12 ms 23764 KB Output is correct
21 Correct 12 ms 23768 KB Output is correct
22 Correct 11 ms 23860 KB Output is correct
23 Correct 11 ms 23848 KB Output is correct
24 Correct 14 ms 23764 KB Output is correct
25 Correct 11 ms 23764 KB Output is correct
26 Correct 11 ms 23764 KB Output is correct
27 Correct 11 ms 23764 KB Output is correct
28 Correct 14 ms 24020 KB Output is correct
29 Correct 16 ms 24076 KB Output is correct
30 Correct 20 ms 24020 KB Output is correct
31 Correct 16 ms 24020 KB Output is correct
32 Correct 19 ms 24092 KB Output is correct
33 Correct 15 ms 24060 KB Output is correct
34 Correct 20 ms 24004 KB Output is correct
35 Correct 272 ms 44416 KB Output is correct
36 Correct 278 ms 45280 KB Output is correct
37 Correct 297 ms 44488 KB Output is correct
38 Correct 272 ms 49836 KB Output is correct
39 Correct 299 ms 45956 KB Output is correct
40 Correct 223 ms 45244 KB Output is correct
41 Correct 556 ms 47792 KB Output is correct
42 Correct 208 ms 40940 KB Output is correct
43 Correct 68 ms 28916 KB Output is correct
44 Correct 387 ms 46352 KB Output is correct
45 Correct 456 ms 46664 KB Output is correct
46 Correct 569 ms 48180 KB Output is correct
47 Correct 519 ms 48112 KB Output is correct
48 Correct 344 ms 44848 KB Output is correct
49 Correct 293 ms 50256 KB Output is correct
50 Correct 491 ms 50188 KB Output is correct
51 Correct 433 ms 50232 KB Output is correct
52 Correct 14 ms 23824 KB Output is correct
53 Correct 592 ms 48148 KB Output is correct
54 Correct 529 ms 46320 KB Output is correct
55 Correct 541 ms 46760 KB Output is correct
56 Correct 542 ms 48588 KB Output is correct
57 Correct 331 ms 44832 KB Output is correct
58 Correct 345 ms 63936 KB Output is correct
59 Correct 390 ms 61852 KB Output is correct
60 Correct 380 ms 61772 KB Output is correct
61 Correct 522 ms 58472 KB Output is correct
62 Correct 12 ms 23764 KB Output is correct
63 Correct 548 ms 61660 KB Output is correct
64 Correct 393 ms 58956 KB Output is correct
65 Correct 460 ms 60196 KB Output is correct
66 Correct 502 ms 55256 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 47132 KB Output is correct
2 Correct 411 ms 47444 KB Output is correct
3 Correct 249 ms 45316 KB Output is correct
4 Correct 346 ms 45572 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 359 ms 46344 KB Output is correct
7 Correct 169 ms 40024 KB Output is correct
8 Correct 66 ms 28448 KB Output is correct
9 Correct 242 ms 45248 KB Output is correct
10 Correct 392 ms 49876 KB Output is correct
11 Correct 227 ms 45256 KB Output is correct
12 Correct 15 ms 23808 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 12 ms 23816 KB Output is correct
15 Correct 12 ms 23840 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 15 ms 23816 KB Output is correct
19 Correct 12 ms 23844 KB Output is correct
20 Correct 12 ms 23764 KB Output is correct
21 Correct 12 ms 23768 KB Output is correct
22 Correct 11 ms 23860 KB Output is correct
23 Correct 11 ms 23848 KB Output is correct
24 Correct 14 ms 23764 KB Output is correct
25 Correct 11 ms 23764 KB Output is correct
26 Correct 11 ms 23764 KB Output is correct
27 Correct 11 ms 23764 KB Output is correct
28 Correct 14 ms 24020 KB Output is correct
29 Correct 16 ms 24076 KB Output is correct
30 Correct 20 ms 24020 KB Output is correct
31 Correct 16 ms 24020 KB Output is correct
32 Correct 19 ms 24092 KB Output is correct
33 Correct 15 ms 24060 KB Output is correct
34 Correct 20 ms 24004 KB Output is correct
35 Correct 272 ms 44416 KB Output is correct
36 Correct 278 ms 45280 KB Output is correct
37 Correct 297 ms 44488 KB Output is correct
38 Correct 272 ms 49836 KB Output is correct
39 Correct 299 ms 45956 KB Output is correct
40 Correct 223 ms 45244 KB Output is correct
41 Correct 556 ms 47792 KB Output is correct
42 Correct 208 ms 40940 KB Output is correct
43 Correct 68 ms 28916 KB Output is correct
44 Correct 387 ms 46352 KB Output is correct
45 Correct 456 ms 46664 KB Output is correct
46 Correct 569 ms 48180 KB Output is correct
47 Correct 519 ms 48112 KB Output is correct
48 Correct 344 ms 44848 KB Output is correct
49 Correct 293 ms 50256 KB Output is correct
50 Correct 491 ms 50188 KB Output is correct
51 Correct 433 ms 50232 KB Output is correct
52 Correct 14 ms 23824 KB Output is correct
53 Correct 592 ms 48148 KB Output is correct
54 Correct 529 ms 46320 KB Output is correct
55 Correct 541 ms 46760 KB Output is correct
56 Correct 542 ms 48588 KB Output is correct
57 Correct 1767 ms 123200 KB Output is correct
58 Correct 1515 ms 150472 KB Output is correct
59 Correct 2087 ms 150360 KB Output is correct
60 Correct 2009 ms 149836 KB Output is correct
61 Correct 3690 ms 139880 KB Output is correct
62 Correct 2353 ms 129348 KB Output is correct
63 Correct 2887 ms 127476 KB Output is correct
64 Correct 3549 ms 139236 KB Output is correct
65 Correct 331 ms 44832 KB Output is correct
66 Correct 345 ms 63936 KB Output is correct
67 Correct 390 ms 61852 KB Output is correct
68 Correct 380 ms 61772 KB Output is correct
69 Correct 522 ms 58472 KB Output is correct
70 Correct 12 ms 23764 KB Output is correct
71 Correct 548 ms 61660 KB Output is correct
72 Correct 393 ms 58956 KB Output is correct
73 Correct 460 ms 60196 KB Output is correct
74 Correct 502 ms 55256 KB Output is correct
75 Correct 1683 ms 177480 KB Output is correct
76 Correct 1536 ms 204844 KB Output is correct
77 Correct 2245 ms 182028 KB Output is correct
78 Correct 2278 ms 181124 KB Output is correct
79 Correct 3606 ms 209788 KB Output is correct
80 Correct 2406 ms 163908 KB Output is correct
81 Correct 3220 ms 173052 KB Output is correct
82 Correct 3426 ms 177684 KB Output is correct
83 Correct 3683 ms 171144 KB Output is correct