oj.uz

Submission #769036

# Submission time Handle Problem Language Result Execution time Memory
769036 2023-06-29T05:24:22 Z nguyentunglam Two Dishes (JOI19_dishes) C++17
74 / 100
 3407 ms 150316 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, 0, 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 352 ms 47436 KB Output is correct
2 Correct 364 ms 47748 KB Output is correct
3 Correct 240 ms 45464 KB Output is correct
4 Correct 287 ms 45968 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 326 ms 46552 KB Output is correct
7 Correct 170 ms 40348 KB Output is correct
8 Correct 73 ms 28916 KB Output is correct
9 Correct 243 ms 45576 KB Output is correct
10 Correct 348 ms 50140 KB Output is correct
11 Correct 212 ms 45612 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 11 ms 23756 KB Output is correct
7 Correct 12 ms 23768 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23756 KB Output is correct
11 Correct 13 ms 23820 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 14 ms 23856 KB Output is correct
14 Correct 10 ms 23816 KB Output is correct
15 Correct 10 ms 23764 KB Output is correct
16 Correct 10 ms 23816 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 11 ms 23756 KB Output is correct
7 Correct 12 ms 23768 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23756 KB Output is correct
11 Correct 13 ms 23820 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 14 ms 23856 KB Output is correct
14 Correct 10 ms 23816 KB Output is correct
15 Correct 10 ms 23764 KB Output is correct
16 Correct 10 ms 23816 KB Output is correct
17 Correct 12 ms 24148 KB Output is correct
18 Correct 13 ms 24096 KB Output is correct
19 Correct 17 ms 24092 KB Output is correct
20 Correct 12 ms 24128 KB Output is correct
21 Correct 13 ms 24096 KB Output is correct
22 Correct 13 ms 24024 KB Output is correct
23 Correct 13 ms 24072 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 11 ms 23756 KB Output is correct
7 Correct 12 ms 23768 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23756 KB Output is correct
11 Correct 13 ms 23820 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 14 ms 23856 KB Output is correct
14 Correct 10 ms 23816 KB Output is correct
15 Correct 10 ms 23764 KB Output is correct
16 Correct 10 ms 23816 KB Output is correct
17 Correct 12 ms 24148 KB Output is correct
18 Correct 13 ms 24096 KB Output is correct
19 Correct 17 ms 24092 KB Output is correct
20 Correct 12 ms 24128 KB Output is correct
21 Correct 13 ms 24096 KB Output is correct
22 Correct 13 ms 24024 KB Output is correct
23 Correct 13 ms 24072 KB Output is correct
24 Correct 269 ms 44680 KB Output is correct
25 Correct 258 ms 45504 KB Output is correct
26 Correct 305 ms 44756 KB Output is correct
27 Correct 267 ms 50084 KB Output is correct
28 Correct 300 ms 46160 KB Output is correct
29 Correct 227 ms 45504 KB Output is correct
30 Correct 494 ms 48016 KB Output is correct
31 Correct 192 ms 40876 KB Output is correct
32 Correct 74 ms 28748 KB Output is correct
33 Correct 349 ms 46232 KB Output is correct
34 Correct 434 ms 46584 KB Output is correct
35 Correct 512 ms 48060 KB Output is correct
36 Correct 473 ms 47968 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 11 ms 23756 KB Output is correct
7 Correct 12 ms 23768 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23756 KB Output is correct
11 Correct 13 ms 23820 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 14 ms 23856 KB Output is correct
14 Correct 10 ms 23816 KB Output is correct
15 Correct 10 ms 23764 KB Output is correct
16 Correct 10 ms 23816 KB Output is correct
17 Correct 12 ms 24148 KB Output is correct
18 Correct 13 ms 24096 KB Output is correct
19 Correct 17 ms 24092 KB Output is correct
20 Correct 12 ms 24128 KB Output is correct
21 Correct 13 ms 24096 KB Output is correct
22 Correct 13 ms 24024 KB Output is correct
23 Correct 13 ms 24072 KB Output is correct
24 Correct 269 ms 44680 KB Output is correct
25 Correct 258 ms 45504 KB Output is correct
26 Correct 305 ms 44756 KB Output is correct
27 Correct 267 ms 50084 KB Output is correct
28 Correct 300 ms 46160 KB Output is correct
29 Correct 227 ms 45504 KB Output is correct
30 Correct 494 ms 48016 KB Output is correct
31 Correct 192 ms 40876 KB Output is correct
32 Correct 74 ms 28748 KB Output is correct
33 Correct 349 ms 46232 KB Output is correct
34 Correct 434 ms 46584 KB Output is correct
35 Correct 512 ms 48060 KB Output is correct
36 Correct 473 ms 47968 KB Output is correct
37 Correct 314 ms 44756 KB Output is correct
38 Correct 278 ms 50036 KB Output is correct
39 Correct 380 ms 50120 KB Output is correct
40 Correct 395 ms 50160 KB Output is correct
41 Correct 13 ms 23764 KB Output is correct
42 Correct 566 ms 48020 KB Output is correct
43 Correct 354 ms 46184 KB Output is correct
44 Correct 499 ms 46400 KB Output is correct
45 Correct 549 ms 47948 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23836 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 11 ms 23756 KB Output is correct
7 Correct 12 ms 23768 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23756 KB Output is correct
11 Correct 13 ms 23820 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 14 ms 23856 KB Output is correct
14 Correct 10 ms 23816 KB Output is correct
15 Correct 10 ms 23764 KB Output is correct
16 Correct 10 ms 23816 KB Output is correct
17 Correct 12 ms 24148 KB Output is correct
18 Correct 13 ms 24096 KB Output is correct
19 Correct 17 ms 24092 KB Output is correct
20 Correct 12 ms 24128 KB Output is correct
21 Correct 13 ms 24096 KB Output is correct
22 Correct 13 ms 24024 KB Output is correct
23 Correct 13 ms 24072 KB Output is correct
24 Correct 269 ms 44680 KB Output is correct
25 Correct 258 ms 45504 KB Output is correct
26 Correct 305 ms 44756 KB Output is correct
27 Correct 267 ms 50084 KB Output is correct
28 Correct 300 ms 46160 KB Output is correct
29 Correct 227 ms 45504 KB Output is correct
30 Correct 494 ms 48016 KB Output is correct
31 Correct 192 ms 40876 KB Output is correct
32 Correct 74 ms 28748 KB Output is correct
33 Correct 349 ms 46232 KB Output is correct
34 Correct 434 ms 46584 KB Output is correct
35 Correct 512 ms 48060 KB Output is correct
36 Correct 473 ms 47968 KB Output is correct
37 Correct 314 ms 44756 KB Output is correct
38 Correct 278 ms 50036 KB Output is correct
39 Correct 380 ms 50120 KB Output is correct
40 Correct 395 ms 50160 KB Output is correct
41 Correct 13 ms 23764 KB Output is correct
42 Correct 566 ms 48020 KB Output is correct
43 Correct 354 ms 46184 KB Output is correct
44 Correct 499 ms 46400 KB Output is correct
45 Correct 549 ms 47948 KB Output is correct
46 Correct 1621 ms 122968 KB Output is correct
47 Correct 1430 ms 150316 KB Output is correct
48 Correct 1903 ms 150088 KB Output is correct
49 Correct 1883 ms 149784 KB Output is correct
50 Correct 3407 ms 139432 KB Output is correct
51 Correct 2070 ms 128904 KB Output is correct
52 Correct 2488 ms 127132 KB Output is correct
53 Correct 3201 ms 139024 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 47436 KB Output is correct
2 Correct 364 ms 47748 KB Output is correct
3 Correct 240 ms 45464 KB Output is correct
4 Correct 287 ms 45968 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 326 ms 46552 KB Output is correct
7 Correct 170 ms 40348 KB Output is correct
8 Correct 73 ms 28916 KB Output is correct
9 Correct 243 ms 45576 KB Output is correct
10 Correct 348 ms 50140 KB Output is correct
11 Correct 212 ms 45612 KB Output is correct
12 Correct 12 ms 23836 KB Output is correct
13 Correct 12 ms 23816 KB Output is correct
14 Correct 12 ms 23764 KB Output is correct
15 Correct 12 ms 23824 KB Output is correct
16 Correct 13 ms 23812 KB Output is correct
17 Correct 11 ms 23756 KB Output is correct
18 Correct 12 ms 23768 KB Output is correct
19 Correct 11 ms 23764 KB Output is correct
20 Correct 12 ms 23764 KB Output is correct
21 Correct 12 ms 23756 KB Output is correct
22 Correct 13 ms 23820 KB Output is correct
23 Correct 10 ms 23764 KB Output is correct
24 Correct 14 ms 23856 KB Output is correct
25 Correct 10 ms 23816 KB Output is correct
26 Correct 10 ms 23764 KB Output is correct
27 Correct 10 ms 23816 KB Output is correct
28 Correct 12 ms 24148 KB Output is correct
29 Correct 13 ms 24096 KB Output is correct
30 Correct 17 ms 24092 KB Output is correct
31 Correct 12 ms 24128 KB Output is correct
32 Correct 13 ms 24096 KB Output is correct
33 Correct 13 ms 24024 KB Output is correct
34 Correct 13 ms 24072 KB Output is correct
35 Correct 269 ms 44680 KB Output is correct
36 Correct 258 ms 45504 KB Output is correct
37 Correct 305 ms 44756 KB Output is correct
38 Correct 267 ms 50084 KB Output is correct
39 Correct 300 ms 46160 KB Output is correct
40 Correct 227 ms 45504 KB Output is correct
41 Correct 494 ms 48016 KB Output is correct
42 Correct 192 ms 40876 KB Output is correct
43 Correct 74 ms 28748 KB Output is correct
44 Correct 349 ms 46232 KB Output is correct
45 Correct 434 ms 46584 KB Output is correct
46 Correct 512 ms 48060 KB Output is correct
47 Correct 473 ms 47968 KB Output is correct
48 Correct 314 ms 44756 KB Output is correct
49 Correct 278 ms 50036 KB Output is correct
50 Correct 380 ms 50120 KB Output is correct
51 Correct 395 ms 50160 KB Output is correct
52 Correct 13 ms 23764 KB Output is correct
53 Correct 566 ms 48020 KB Output is correct
54 Correct 354 ms 46184 KB Output is correct
55 Correct 499 ms 46400 KB Output is correct
56 Correct 549 ms 47948 KB Output is correct
57 Incorrect 313 ms 44488 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 47436 KB Output is correct
2 Correct 364 ms 47748 KB Output is correct
3 Correct 240 ms 45464 KB Output is correct
4 Correct 287 ms 45968 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 326 ms 46552 KB Output is correct
7 Correct 170 ms 40348 KB Output is correct
8 Correct 73 ms 28916 KB Output is correct
9 Correct 243 ms 45576 KB Output is correct
10 Correct 348 ms 50140 KB Output is correct
11 Correct 212 ms 45612 KB Output is correct
12 Correct 12 ms 23836 KB Output is correct
13 Correct 12 ms 23816 KB Output is correct
14 Correct 12 ms 23764 KB Output is correct
15 Correct 12 ms 23824 KB Output is correct
16 Correct 13 ms 23812 KB Output is correct
17 Correct 11 ms 23756 KB Output is correct
18 Correct 12 ms 23768 KB Output is correct
19 Correct 11 ms 23764 KB Output is correct
20 Correct 12 ms 23764 KB Output is correct
21 Correct 12 ms 23756 KB Output is correct
22 Correct 13 ms 23820 KB Output is correct
23 Correct 10 ms 23764 KB Output is correct
24 Correct 14 ms 23856 KB Output is correct
25 Correct 10 ms 23816 KB Output is correct
26 Correct 10 ms 23764 KB Output is correct
27 Correct 10 ms 23816 KB Output is correct
28 Correct 12 ms 24148 KB Output is correct
29 Correct 13 ms 24096 KB Output is correct
30 Correct 17 ms 24092 KB Output is correct
31 Correct 12 ms 24128 KB Output is correct
32 Correct 13 ms 24096 KB Output is correct
33 Correct 13 ms 24024 KB Output is correct
34 Correct 13 ms 24072 KB Output is correct
35 Correct 269 ms 44680 KB Output is correct
36 Correct 258 ms 45504 KB Output is correct
37 Correct 305 ms 44756 KB Output is correct
38 Correct 267 ms 50084 KB Output is correct
39 Correct 300 ms 46160 KB Output is correct
40 Correct 227 ms 45504 KB Output is correct
41 Correct 494 ms 48016 KB Output is correct
42 Correct 192 ms 40876 KB Output is correct
43 Correct 74 ms 28748 KB Output is correct
44 Correct 349 ms 46232 KB Output is correct
45 Correct 434 ms 46584 KB Output is correct
46 Correct 512 ms 48060 KB Output is correct
47 Correct 473 ms 47968 KB Output is correct
48 Correct 314 ms 44756 KB Output is correct
49 Correct 278 ms 50036 KB Output is correct
50 Correct 380 ms 50120 KB Output is correct
51 Correct 395 ms 50160 KB Output is correct
52 Correct 13 ms 23764 KB Output is correct
53 Correct 566 ms 48020 KB Output is correct
54 Correct 354 ms 46184 KB Output is correct
55 Correct 499 ms 46400 KB Output is correct
56 Correct 549 ms 47948 KB Output is correct
57 Correct 1621 ms 122968 KB Output is correct
58 Correct 1430 ms 150316 KB Output is correct
59 Correct 1903 ms 150088 KB Output is correct
60 Correct 1883 ms 149784 KB Output is correct
61 Correct 3407 ms 139432 KB Output is correct
62 Correct 2070 ms 128904 KB Output is correct
63 Correct 2488 ms 127132 KB Output is correct
64 Correct 3201 ms 139024 KB Output is correct
65 Incorrect 313 ms 44488 KB Output isn't correct
66 Halted 0 ms 0 KB -