oj.uz

Submission #170779

# Submission time Handle Problem Language Result Execution time Memory
170779 2019-12-26T10:44:32 Z gs18103 Two Dishes (JOI19_dishes) C++14
82 / 100
 7744 ms 198440 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define my_assert cout << "!" << endl;

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 1010101;
const int INF = (1 << 30) - 1;
const ll LINF = 1LL << 60;

int n, m;
ll A[MAX], S[MAX], P[MAX];
ll B[MAX], T[MAX], Q[MAX];
ll sumA[MAX], sumB[MAX], ans;
ll tree[4*MAX], lazy1[4*MAX], lazy2[4*MAX];

void update_lazy(int node, int s, int e) {
    tree[node] = tree[node] * lazy2[node] + lazy1[node];
    if(s != e) {
        if(lazy2[node] == 1) {
            lazy1[node*2] += lazy1[node];
            lazy1[node*2+1] += lazy1[node];
        }
        else {
            lazy1[node*2] = lazy1[node], lazy2[node*2] = 0;
            lazy1[node*2+1] = lazy1[node], lazy2[node*2+1] = 0;
        }
    }
    lazy1[node] = 0;
    lazy2[node] = 1;
}

void update1(int node, int s, int e, int r, ll val) {
    update_lazy(node, s, e);
    if(s > r) return;
    if(e <= r) {
        lazy1[node] += val;
        update_lazy(node, s, e);
        return;
    }
    int mi = (s + e) / 2;
    update1(node*2, s, mi, r, val);
    update1(node*2+1, mi+1, e, r, val);
    tree[node] = max(tree[node*2], tree[node*2+1]);
}

void update2(int node, int s, int e, int l, int r, ll a, ll b) {
    update_lazy(node, s, e);
    if(s > r || e < l) return;
    if(s >= l && e <= r) {
        lazy2[node] = a;
        lazy1[node] = b;
        update_lazy(node, s, e);
        return;
    }
    int mi = (s + e) / 2;
    update2(node*2, s, mi, l, r, a, b);
    update2(node*2+1, mi+1, e, l, r, a, b);
    tree[node] = max(tree[node*2], tree[node*2+1]);
}

ll cal(int node, int s, int e, int l, int r) {
    update_lazy(node, s, e);
    if(s > r || e < l) return -LINF;
    if(s >= l && e <= r) return tree[node];
    int mi = (s + e) / 2;
    return max(cal(node*2, s, mi, l, r), cal(node*2+1, mi+1, e, l, r));
}

int get(int node, int s, int e, ll val) {
    update_lazy(node, s, e);
    if(s == e) return s;
    update_lazy(node*2, s, e);
    if(tree[node*2] > val) return get(node*2, s, (s+e)/2, val);
    else return get(node*2+1, (s+e)/2+1, e, val);
}

struct point {
    int x, y; ll val;
    point(int x, int y, ll val) : x(x), y(y), val(val) {}
};
vector <point> po;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    for(int i = 1; i < 4 * MAX; i++) lazy2[i] = 1;

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> A[i] >> S[i] >> P[i];
        sumA[i] = sumA[i-1] + A[i];
    }
    for(int i = 1; i <= m; i++) {
        cin >> B[i] >> T[i] >> Q[i];
        sumB[i] = sumB[i-1] + B[i];
        ans += Q[i];
    }
    for(int i = 1; i <= n; i++) {
        int temp = upper_bound(sumB, sumB+m+1, S[i] - sumA[i]) - sumB - 1;
        if(temp >= 0) po.eb(i, temp, P[i]);
    }
    for(int i = 1; i <= m; i++) {
        int temp = upper_bound(sumA, sumA+n+1, T[i] - sumB[i]) - sumA - 1;
        if(temp < 0) ans -= Q[i];
        else if(temp < n) po.eb(temp+1, i-1, -Q[i]);
    }
    sort(all(po), [](point a, point b) {
        if(a.x == b.x) return a.y > b.y;
        return a.x < b.x;
    });

    ll rem = 0;
    for(int i = 0; i < po.size(); i++) {
        if(i+1 < po.size() && po[i].x == po[i+1].x && po[i].y == po[i+1].y) {
            rem += po[i].val;
            continue;
        }
        update1(1, 0, m, po[i].y, po[i].val + rem);
        ll temp = cal(1, 0, m, 0, po[i].y);
        int idx = m + 1;
        if(tree[1] > temp) idx = get(1, 0, m, temp);
        update2(1, 0, m, po[i].y+1, idx - 1, 0, temp);
        rem = 0;
    }
    cout << cal(1, 0, m, m, m) + ans;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:120:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < po.size(); i++) {
                    ~~^~~~~~~~~~~
dishes.cpp:121:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i+1 < po.size() && po[i].x == po[i+1].x && po[i].y == po[i+1].y) {
            ~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 63528 KB Output is correct
2 Correct 618 ms 67132 KB Output is correct
3 Correct 275 ms 55096 KB Output is correct
4 Correct 474 ms 62688 KB Output is correct
5 Correct 28 ms 32092 KB Output is correct
6 Correct 580 ms 65024 KB Output is correct
7 Correct 136 ms 44624 KB Output is correct
8 Correct 153 ms 48740 KB Output is correct
9 Correct 298 ms 55000 KB Output is correct
10 Correct 554 ms 70080 KB Output is correct
11 Correct 198 ms 55568 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32080 KB Output is correct
2 Correct 27 ms 32064 KB Output is correct
3 Correct 27 ms 31980 KB Output is correct
4 Correct 27 ms 31984 KB Output is correct
5 Correct 27 ms 32080 KB Output is correct
6 Correct 26 ms 31992 KB Output is correct
7 Correct 27 ms 31992 KB Output is correct
8 Correct 26 ms 31992 KB Output is correct
9 Correct 27 ms 32092 KB Output is correct
10 Correct 27 ms 31992 KB Output is correct
11 Correct 27 ms 32036 KB Output is correct
12 Correct 27 ms 32040 KB Output is correct
13 Correct 28 ms 31992 KB Output is correct
14 Correct 27 ms 32040 KB Output is correct
15 Correct 27 ms 31992 KB Output is correct
16 Correct 27 ms 31992 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32080 KB Output is correct
2 Correct 27 ms 32064 KB Output is correct
3 Correct 27 ms 31980 KB Output is correct
4 Correct 27 ms 31984 KB Output is correct
5 Correct 27 ms 32080 KB Output is correct
6 Correct 26 ms 31992 KB Output is correct
7 Correct 27 ms 31992 KB Output is correct
8 Correct 26 ms 31992 KB Output is correct
9 Correct 27 ms 32092 KB Output is correct
10 Correct 27 ms 31992 KB Output is correct
11 Correct 27 ms 32036 KB Output is correct
12 Correct 27 ms 32040 KB Output is correct
13 Correct 28 ms 31992 KB Output is correct
14 Correct 27 ms 32040 KB Output is correct
15 Correct 27 ms 31992 KB Output is correct
16 Correct 27 ms 31992 KB Output is correct
17 Correct 31 ms 32400 KB Output is correct
18 Correct 31 ms 32508 KB Output is correct
19 Correct 33 ms 32504 KB Output is correct
20 Correct 31 ms 32376 KB Output is correct
21 Correct 33 ms 32508 KB Output is correct
22 Correct 33 ms 32376 KB Output is correct
23 Correct 32 ms 32380 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32080 KB Output is correct
2 Correct 27 ms 32064 KB Output is correct
3 Correct 27 ms 31980 KB Output is correct
4 Correct 27 ms 31984 KB Output is correct
5 Correct 27 ms 32080 KB Output is correct
6 Correct 26 ms 31992 KB Output is correct
7 Correct 27 ms 31992 KB Output is correct
8 Correct 26 ms 31992 KB Output is correct
9 Correct 27 ms 32092 KB Output is correct
10 Correct 27 ms 31992 KB Output is correct
11 Correct 27 ms 32036 KB Output is correct
12 Correct 27 ms 32040 KB Output is correct
13 Correct 28 ms 31992 KB Output is correct
14 Correct 27 ms 32040 KB Output is correct
15 Correct 27 ms 31992 KB Output is correct
16 Correct 27 ms 31992 KB Output is correct
17 Correct 31 ms 32400 KB Output is correct
18 Correct 31 ms 32508 KB Output is correct
19 Correct 33 ms 32504 KB Output is correct
20 Correct 31 ms 32376 KB Output is correct
21 Correct 33 ms 32508 KB Output is correct
22 Correct 33 ms 32376 KB Output is correct
23 Correct 32 ms 32380 KB Output is correct
24 Correct 485 ms 50088 KB Output is correct
25 Correct 532 ms 62888 KB Output is correct
26 Correct 480 ms 57224 KB Output is correct
27 Correct 541 ms 62832 KB Output is correct
28 Correct 514 ms 61712 KB Output is correct
29 Correct 247 ms 49996 KB Output is correct
30 Correct 1184 ms 64192 KB Output is correct
31 Correct 272 ms 53696 KB Output is correct
32 Correct 157 ms 44008 KB Output is correct
33 Correct 715 ms 61340 KB Output is correct
34 Correct 920 ms 63792 KB Output is correct
35 Correct 1132 ms 64400 KB Output is correct
36 Correct 1101 ms 63372 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32080 KB Output is correct
2 Correct 27 ms 32064 KB Output is correct
3 Correct 27 ms 31980 KB Output is correct
4 Correct 27 ms 31984 KB Output is correct
5 Correct 27 ms 32080 KB Output is correct
6 Correct 26 ms 31992 KB Output is correct
7 Correct 27 ms 31992 KB Output is correct
8 Correct 26 ms 31992 KB Output is correct
9 Correct 27 ms 32092 KB Output is correct
10 Correct 27 ms 31992 KB Output is correct
11 Correct 27 ms 32036 KB Output is correct
12 Correct 27 ms 32040 KB Output is correct
13 Correct 28 ms 31992 KB Output is correct
14 Correct 27 ms 32040 KB Output is correct
15 Correct 27 ms 31992 KB Output is correct
16 Correct 27 ms 31992 KB Output is correct
17 Correct 31 ms 32400 KB Output is correct
18 Correct 31 ms 32508 KB Output is correct
19 Correct 33 ms 32504 KB Output is correct
20 Correct 31 ms 32376 KB Output is correct
21 Correct 33 ms 32508 KB Output is correct
22 Correct 33 ms 32376 KB Output is correct
23 Correct 32 ms 32380 KB Output is correct
24 Correct 485 ms 50088 KB Output is correct
25 Correct 532 ms 62888 KB Output is correct
26 Correct 480 ms 57224 KB Output is correct
27 Correct 541 ms 62832 KB Output is correct
28 Correct 514 ms 61712 KB Output is correct
29 Correct 247 ms 49996 KB Output is correct
30 Correct 1184 ms 64192 KB Output is correct
31 Correct 272 ms 53696 KB Output is correct
32 Correct 157 ms 44008 KB Output is correct
33 Correct 715 ms 61340 KB Output is correct
34 Correct 920 ms 63792 KB Output is correct
35 Correct 1132 ms 64400 KB Output is correct
36 Correct 1101 ms 63372 KB Output is correct
37 Correct 507 ms 57192 KB Output is correct
38 Correct 579 ms 75392 KB Output is correct
39 Correct 592 ms 74408 KB Output is correct
40 Correct 685 ms 70248 KB Output is correct
41 Correct 27 ms 32120 KB Output is correct
42 Correct 1235 ms 76832 KB Output is correct
43 Correct 750 ms 73280 KB Output is correct
44 Correct 935 ms 75844 KB Output is correct
45 Correct 1169 ms 70548 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32080 KB Output is correct
2 Correct 27 ms 32064 KB Output is correct
3 Correct 27 ms 31980 KB Output is correct
4 Correct 27 ms 31984 KB Output is correct
5 Correct 27 ms 32080 KB Output is correct
6 Correct 26 ms 31992 KB Output is correct
7 Correct 27 ms 31992 KB Output is correct
8 Correct 26 ms 31992 KB Output is correct
9 Correct 27 ms 32092 KB Output is correct
10 Correct 27 ms 31992 KB Output is correct
11 Correct 27 ms 32036 KB Output is correct
12 Correct 27 ms 32040 KB Output is correct
13 Correct 28 ms 31992 KB Output is correct
14 Correct 27 ms 32040 KB Output is correct
15 Correct 27 ms 31992 KB Output is correct
16 Correct 27 ms 31992 KB Output is correct
17 Correct 31 ms 32400 KB Output is correct
18 Correct 31 ms 32508 KB Output is correct
19 Correct 33 ms 32504 KB Output is correct
20 Correct 31 ms 32376 KB Output is correct
21 Correct 33 ms 32508 KB Output is correct
22 Correct 33 ms 32376 KB Output is correct
23 Correct 32 ms 32380 KB Output is correct
24 Correct 485 ms 50088 KB Output is correct
25 Correct 532 ms 62888 KB Output is correct
26 Correct 480 ms 57224 KB Output is correct
27 Correct 541 ms 62832 KB Output is correct
28 Correct 514 ms 61712 KB Output is correct
29 Correct 247 ms 49996 KB Output is correct
30 Correct 1184 ms 64192 KB Output is correct
31 Correct 272 ms 53696 KB Output is correct
32 Correct 157 ms 44008 KB Output is correct
33 Correct 715 ms 61340 KB Output is correct
34 Correct 920 ms 63792 KB Output is correct
35 Correct 1132 ms 64400 KB Output is correct
36 Correct 1101 ms 63372 KB Output is correct
37 Correct 507 ms 57192 KB Output is correct
38 Correct 579 ms 75392 KB Output is correct
39 Correct 592 ms 74408 KB Output is correct
40 Correct 685 ms 70248 KB Output is correct
41 Correct 27 ms 32120 KB Output is correct
42 Correct 1235 ms 76832 KB Output is correct
43 Correct 750 ms 73280 KB Output is correct
44 Correct 935 ms 75844 KB Output is correct
45 Correct 1169 ms 70548 KB Output is correct
46 Correct 2634 ms 174384 KB Output is correct
47 Correct 3084 ms 197284 KB Output is correct
48 Correct 3144 ms 194860 KB Output is correct
49 Correct 3665 ms 188776 KB Output is correct
50 Incorrect 7744 ms 198440 KB Output isn't correct
51 Halted 0 ms 0 KB -

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 63528 KB Output is correct
2 Correct 618 ms 67132 KB Output is correct
3 Correct 275 ms 55096 KB Output is correct
4 Correct 474 ms 62688 KB Output is correct
5 Correct 28 ms 32092 KB Output is correct
6 Correct 580 ms 65024 KB Output is correct
7 Correct 136 ms 44624 KB Output is correct
8 Correct 153 ms 48740 KB Output is correct
9 Correct 298 ms 55000 KB Output is correct
10 Correct 554 ms 70080 KB Output is correct
11 Correct 198 ms 55568 KB Output is correct
12 Correct 27 ms 32080 KB Output is correct
13 Correct 27 ms 32064 KB Output is correct
14 Correct 27 ms 31980 KB Output is correct
15 Correct 27 ms 31984 KB Output is correct
16 Correct 27 ms 32080 KB Output is correct
17 Correct 26 ms 31992 KB Output is correct
18 Correct 27 ms 31992 KB Output is correct
19 Correct 26 ms 31992 KB Output is correct
20 Correct 27 ms 32092 KB Output is correct
21 Correct 27 ms 31992 KB Output is correct
22 Correct 27 ms 32036 KB Output is correct
23 Correct 27 ms 32040 KB Output is correct
24 Correct 28 ms 31992 KB Output is correct
25 Correct 27 ms 32040 KB Output is correct
26 Correct 27 ms 31992 KB Output is correct
27 Correct 27 ms 31992 KB Output is correct
28 Correct 31 ms 32400 KB Output is correct
29 Correct 31 ms 32508 KB Output is correct
30 Correct 33 ms 32504 KB Output is correct
31 Correct 31 ms 32376 KB Output is correct
32 Correct 33 ms 32508 KB Output is correct
33 Correct 33 ms 32376 KB Output is correct
34 Correct 32 ms 32380 KB Output is correct
35 Correct 485 ms 50088 KB Output is correct
36 Correct 532 ms 62888 KB Output is correct
37 Correct 480 ms 57224 KB Output is correct
38 Correct 541 ms 62832 KB Output is correct
39 Correct 514 ms 61712 KB Output is correct
40 Correct 247 ms 49996 KB Output is correct
41 Correct 1184 ms 64192 KB Output is correct
42 Correct 272 ms 53696 KB Output is correct
43 Correct 157 ms 44008 KB Output is correct
44 Correct 715 ms 61340 KB Output is correct
45 Correct 920 ms 63792 KB Output is correct
46 Correct 1132 ms 64400 KB Output is correct
47 Correct 1101 ms 63372 KB Output is correct
48 Correct 507 ms 57192 KB Output is correct
49 Correct 579 ms 75392 KB Output is correct
50 Correct 592 ms 74408 KB Output is correct
51 Correct 685 ms 70248 KB Output is correct
52 Correct 27 ms 32120 KB Output is correct
53 Correct 1235 ms 76832 KB Output is correct
54 Correct 750 ms 73280 KB Output is correct
55 Correct 935 ms 75844 KB Output is correct
56 Correct 1169 ms 70548 KB Output is correct
57 Correct 555 ms 74224 KB Output is correct
58 Correct 541 ms 71772 KB Output is correct
59 Correct 692 ms 71352 KB Output is correct
60 Correct 608 ms 75216 KB Output is correct
61 Correct 1048 ms 69864 KB Output is correct
62 Correct 28 ms 31992 KB Output is correct
63 Correct 1228 ms 77004 KB Output is correct
64 Correct 733 ms 73304 KB Output is correct
65 Correct 994 ms 75604 KB Output is correct
66 Correct 1126 ms 70584 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 63528 KB Output is correct
2 Correct 618 ms 67132 KB Output is correct
3 Correct 275 ms 55096 KB Output is correct
4 Correct 474 ms 62688 KB Output is correct
5 Correct 28 ms 32092 KB Output is correct
6 Correct 580 ms 65024 KB Output is correct
7 Correct 136 ms 44624 KB Output is correct
8 Correct 153 ms 48740 KB Output is correct
9 Correct 298 ms 55000 KB Output is correct
10 Correct 554 ms 70080 KB Output is correct
11 Correct 198 ms 55568 KB Output is correct
12 Correct 27 ms 32080 KB Output is correct
13 Correct 27 ms 32064 KB Output is correct
14 Correct 27 ms 31980 KB Output is correct
15 Correct 27 ms 31984 KB Output is correct
16 Correct 27 ms 32080 KB Output is correct
17 Correct 26 ms 31992 KB Output is correct
18 Correct 27 ms 31992 KB Output is correct
19 Correct 26 ms 31992 KB Output is correct
20 Correct 27 ms 32092 KB Output is correct
21 Correct 27 ms 31992 KB Output is correct
22 Correct 27 ms 32036 KB Output is correct
23 Correct 27 ms 32040 KB Output is correct
24 Correct 28 ms 31992 KB Output is correct
25 Correct 27 ms 32040 KB Output is correct
26 Correct 27 ms 31992 KB Output is correct
27 Correct 27 ms 31992 KB Output is correct
28 Correct 31 ms 32400 KB Output is correct
29 Correct 31 ms 32508 KB Output is correct
30 Correct 33 ms 32504 KB Output is correct
31 Correct 31 ms 32376 KB Output is correct
32 Correct 33 ms 32508 KB Output is correct
33 Correct 33 ms 32376 KB Output is correct
34 Correct 32 ms 32380 KB Output is correct
35 Correct 485 ms 50088 KB Output is correct
36 Correct 532 ms 62888 KB Output is correct
37 Correct 480 ms 57224 KB Output is correct
38 Correct 541 ms 62832 KB Output is correct
39 Correct 514 ms 61712 KB Output is correct
40 Correct 247 ms 49996 KB Output is correct
41 Correct 1184 ms 64192 KB Output is correct
42 Correct 272 ms 53696 KB Output is correct
43 Correct 157 ms 44008 KB Output is correct
44 Correct 715 ms 61340 KB Output is correct
45 Correct 920 ms 63792 KB Output is correct
46 Correct 1132 ms 64400 KB Output is correct
47 Correct 1101 ms 63372 KB Output is correct
48 Correct 507 ms 57192 KB Output is correct
49 Correct 579 ms 75392 KB Output is correct
50 Correct 592 ms 74408 KB Output is correct
51 Correct 685 ms 70248 KB Output is correct
52 Correct 27 ms 32120 KB Output is correct
53 Correct 1235 ms 76832 KB Output is correct
54 Correct 750 ms 73280 KB Output is correct
55 Correct 935 ms 75844 KB Output is correct
56 Correct 1169 ms 70548 KB Output is correct
57 Correct 2634 ms 174384 KB Output is correct
58 Correct 3084 ms 197284 KB Output is correct
59 Correct 3144 ms 194860 KB Output is correct
60 Correct 3665 ms 188776 KB Output is correct
61 Incorrect 7744 ms 198440 KB Output isn't correct
62 Halted 0 ms 0 KB -