oj.uz

Submission #170781

# Submission time Handle Problem Language Result Execution time Memory
170781 2019-12-26T10:46:13 Z gs18103 Two Dishes (JOI19_dishes) C++14
82 / 100
 7634 ms 176308 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(cal(1, 0, m, 0, m) > 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 656 ms 68876 KB Output is correct
2 Correct 624 ms 70804 KB Output is correct
3 Correct 270 ms 60188 KB Output is correct
4 Correct 475 ms 65876 KB Output is correct
5 Correct 28 ms 32024 KB Output is correct
6 Correct 581 ms 68776 KB Output is correct
7 Correct 132 ms 44956 KB Output is correct
8 Correct 154 ms 47140 KB Output is correct
9 Correct 274 ms 59020 KB Output is correct
10 Correct 558 ms 69920 KB Output is correct
11 Correct 199 ms 54656 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31992 KB Output is correct
2 Correct 27 ms 31992 KB Output is correct
3 Correct 27 ms 31992 KB Output is correct
4 Correct 27 ms 32064 KB Output is correct
5 Correct 28 ms 31992 KB Output is correct
6 Correct 27 ms 31992 KB Output is correct
7 Correct 27 ms 31992 KB Output is correct
8 Correct 27 ms 31992 KB Output is correct
9 Correct 28 ms 32036 KB Output is correct
10 Correct 28 ms 32092 KB Output is correct
11 Correct 28 ms 32084 KB Output is correct
12 Correct 27 ms 31992 KB Output is correct
13 Correct 27 ms 31992 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 31972 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 31992 KB Output is correct
2 Correct 27 ms 31992 KB Output is correct
3 Correct 27 ms 31992 KB Output is correct
4 Correct 27 ms 32064 KB Output is correct
5 Correct 28 ms 31992 KB Output is correct
6 Correct 27 ms 31992 KB Output is correct
7 Correct 27 ms 31992 KB Output is correct
8 Correct 27 ms 31992 KB Output is correct
9 Correct 28 ms 32036 KB Output is correct
10 Correct 28 ms 32092 KB Output is correct
11 Correct 28 ms 32084 KB Output is correct
12 Correct 27 ms 31992 KB Output is correct
13 Correct 27 ms 31992 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 31972 KB Output is correct
16 Correct 27 ms 31992 KB Output is correct
17 Correct 30 ms 32464 KB Output is correct
18 Correct 31 ms 32432 KB Output is correct
19 Correct 34 ms 32492 KB Output is correct
20 Correct 32 ms 32376 KB Output is correct
21 Correct 33 ms 32412 KB Output is correct
22 Correct 33 ms 32376 KB Output is correct
23 Correct 34 ms 32448 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31992 KB Output is correct
2 Correct 27 ms 31992 KB Output is correct
3 Correct 27 ms 31992 KB Output is correct
4 Correct 27 ms 32064 KB Output is correct
5 Correct 28 ms 31992 KB Output is correct
6 Correct 27 ms 31992 KB Output is correct
7 Correct 27 ms 31992 KB Output is correct
8 Correct 27 ms 31992 KB Output is correct
9 Correct 28 ms 32036 KB Output is correct
10 Correct 28 ms 32092 KB Output is correct
11 Correct 28 ms 32084 KB Output is correct
12 Correct 27 ms 31992 KB Output is correct
13 Correct 27 ms 31992 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 31972 KB Output is correct
16 Correct 27 ms 31992 KB Output is correct
17 Correct 30 ms 32464 KB Output is correct
18 Correct 31 ms 32432 KB Output is correct
19 Correct 34 ms 32492 KB Output is correct
20 Correct 32 ms 32376 KB Output is correct
21 Correct 33 ms 32412 KB Output is correct
22 Correct 33 ms 32376 KB Output is correct
23 Correct 34 ms 32448 KB Output is correct
24 Correct 493 ms 55992 KB Output is correct
25 Correct 541 ms 68820 KB Output is correct
26 Correct 491 ms 63172 KB Output is correct
27 Correct 551 ms 68764 KB Output is correct
28 Correct 507 ms 67716 KB Output is correct
29 Correct 247 ms 55940 KB Output is correct
30 Correct 1207 ms 70236 KB Output is correct
31 Correct 276 ms 57572 KB Output is correct
32 Correct 157 ms 47708 KB Output is correct
33 Correct 716 ms 67132 KB Output is correct
34 Correct 927 ms 69580 KB Output is correct
35 Correct 1143 ms 67460 KB Output is correct
36 Correct 1103 ms 66296 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31992 KB Output is correct
2 Correct 27 ms 31992 KB Output is correct
3 Correct 27 ms 31992 KB Output is correct
4 Correct 27 ms 32064 KB Output is correct
5 Correct 28 ms 31992 KB Output is correct
6 Correct 27 ms 31992 KB Output is correct
7 Correct 27 ms 31992 KB Output is correct
8 Correct 27 ms 31992 KB Output is correct
9 Correct 28 ms 32036 KB Output is correct
10 Correct 28 ms 32092 KB Output is correct
11 Correct 28 ms 32084 KB Output is correct
12 Correct 27 ms 31992 KB Output is correct
13 Correct 27 ms 31992 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 31972 KB Output is correct
16 Correct 27 ms 31992 KB Output is correct
17 Correct 30 ms 32464 KB Output is correct
18 Correct 31 ms 32432 KB Output is correct
19 Correct 34 ms 32492 KB Output is correct
20 Correct 32 ms 32376 KB Output is correct
21 Correct 33 ms 32412 KB Output is correct
22 Correct 33 ms 32376 KB Output is correct
23 Correct 34 ms 32448 KB Output is correct
24 Correct 493 ms 55992 KB Output is correct
25 Correct 541 ms 68820 KB Output is correct
26 Correct 491 ms 63172 KB Output is correct
27 Correct 551 ms 68764 KB Output is correct
28 Correct 507 ms 67716 KB Output is correct
29 Correct 247 ms 55940 KB Output is correct
30 Correct 1207 ms 70236 KB Output is correct
31 Correct 276 ms 57572 KB Output is correct
32 Correct 157 ms 47708 KB Output is correct
33 Correct 716 ms 67132 KB Output is correct
34 Correct 927 ms 69580 KB Output is correct
35 Correct 1143 ms 67460 KB Output is correct
36 Correct 1103 ms 66296 KB Output is correct
37 Correct 513 ms 63072 KB Output is correct
38 Correct 585 ms 67720 KB Output is correct
39 Correct 610 ms 69328 KB Output is correct
40 Correct 684 ms 65172 KB Output is correct
41 Correct 27 ms 31980 KB Output is correct
42 Correct 1217 ms 69304 KB Output is correct
43 Correct 737 ms 66060 KB Output is correct
44 Correct 923 ms 68348 KB Output is correct
45 Correct 1199 ms 69480 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31992 KB Output is correct
2 Correct 27 ms 31992 KB Output is correct
3 Correct 27 ms 31992 KB Output is correct
4 Correct 27 ms 32064 KB Output is correct
5 Correct 28 ms 31992 KB Output is correct
6 Correct 27 ms 31992 KB Output is correct
7 Correct 27 ms 31992 KB Output is correct
8 Correct 27 ms 31992 KB Output is correct
9 Correct 28 ms 32036 KB Output is correct
10 Correct 28 ms 32092 KB Output is correct
11 Correct 28 ms 32084 KB Output is correct
12 Correct 27 ms 31992 KB Output is correct
13 Correct 27 ms 31992 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 31972 KB Output is correct
16 Correct 27 ms 31992 KB Output is correct
17 Correct 30 ms 32464 KB Output is correct
18 Correct 31 ms 32432 KB Output is correct
19 Correct 34 ms 32492 KB Output is correct
20 Correct 32 ms 32376 KB Output is correct
21 Correct 33 ms 32412 KB Output is correct
22 Correct 33 ms 32376 KB Output is correct
23 Correct 34 ms 32448 KB Output is correct
24 Correct 493 ms 55992 KB Output is correct
25 Correct 541 ms 68820 KB Output is correct
26 Correct 491 ms 63172 KB Output is correct
27 Correct 551 ms 68764 KB Output is correct
28 Correct 507 ms 67716 KB Output is correct
29 Correct 247 ms 55940 KB Output is correct
30 Correct 1207 ms 70236 KB Output is correct
31 Correct 276 ms 57572 KB Output is correct
32 Correct 157 ms 47708 KB Output is correct
33 Correct 716 ms 67132 KB Output is correct
34 Correct 927 ms 69580 KB Output is correct
35 Correct 1143 ms 67460 KB Output is correct
36 Correct 1103 ms 66296 KB Output is correct
37 Correct 513 ms 63072 KB Output is correct
38 Correct 585 ms 67720 KB Output is correct
39 Correct 610 ms 69328 KB Output is correct
40 Correct 684 ms 65172 KB Output is correct
41 Correct 27 ms 31980 KB Output is correct
42 Correct 1217 ms 69304 KB Output is correct
43 Correct 737 ms 66060 KB Output is correct
44 Correct 923 ms 68348 KB Output is correct
45 Correct 1199 ms 69480 KB Output is correct
46 Correct 2654 ms 146320 KB Output is correct
47 Correct 3104 ms 166772 KB Output is correct
48 Correct 3151 ms 176308 KB Output is correct
49 Correct 3734 ms 159216 KB Output is correct
50 Incorrect 7634 ms 175472 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 656 ms 68876 KB Output is correct
2 Correct 624 ms 70804 KB Output is correct
3 Correct 270 ms 60188 KB Output is correct
4 Correct 475 ms 65876 KB Output is correct
5 Correct 28 ms 32024 KB Output is correct
6 Correct 581 ms 68776 KB Output is correct
7 Correct 132 ms 44956 KB Output is correct
8 Correct 154 ms 47140 KB Output is correct
9 Correct 274 ms 59020 KB Output is correct
10 Correct 558 ms 69920 KB Output is correct
11 Correct 199 ms 54656 KB Output is correct
12 Correct 27 ms 31992 KB Output is correct
13 Correct 27 ms 31992 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 32064 KB Output is correct
16 Correct 28 ms 31992 KB Output is correct
17 Correct 27 ms 31992 KB Output is correct
18 Correct 27 ms 31992 KB Output is correct
19 Correct 27 ms 31992 KB Output is correct
20 Correct 28 ms 32036 KB Output is correct
21 Correct 28 ms 32092 KB Output is correct
22 Correct 28 ms 32084 KB Output is correct
23 Correct 27 ms 31992 KB Output is correct
24 Correct 27 ms 31992 KB Output is correct
25 Correct 27 ms 31992 KB Output is correct
26 Correct 27 ms 31972 KB Output is correct
27 Correct 27 ms 31992 KB Output is correct
28 Correct 30 ms 32464 KB Output is correct
29 Correct 31 ms 32432 KB Output is correct
30 Correct 34 ms 32492 KB Output is correct
31 Correct 32 ms 32376 KB Output is correct
32 Correct 33 ms 32412 KB Output is correct
33 Correct 33 ms 32376 KB Output is correct
34 Correct 34 ms 32448 KB Output is correct
35 Correct 493 ms 55992 KB Output is correct
36 Correct 541 ms 68820 KB Output is correct
37 Correct 491 ms 63172 KB Output is correct
38 Correct 551 ms 68764 KB Output is correct
39 Correct 507 ms 67716 KB Output is correct
40 Correct 247 ms 55940 KB Output is correct
41 Correct 1207 ms 70236 KB Output is correct
42 Correct 276 ms 57572 KB Output is correct
43 Correct 157 ms 47708 KB Output is correct
44 Correct 716 ms 67132 KB Output is correct
45 Correct 927 ms 69580 KB Output is correct
46 Correct 1143 ms 67460 KB Output is correct
47 Correct 1103 ms 66296 KB Output is correct
48 Correct 513 ms 63072 KB Output is correct
49 Correct 585 ms 67720 KB Output is correct
50 Correct 610 ms 69328 KB Output is correct
51 Correct 684 ms 65172 KB Output is correct
52 Correct 27 ms 31980 KB Output is correct
53 Correct 1217 ms 69304 KB Output is correct
54 Correct 737 ms 66060 KB Output is correct
55 Correct 923 ms 68348 KB Output is correct
56 Correct 1199 ms 69480 KB Output is correct
57 Correct 561 ms 64192 KB Output is correct
58 Correct 545 ms 62480 KB Output is correct
59 Correct 696 ms 64016 KB Output is correct
60 Correct 609 ms 68188 KB Output is correct
61 Correct 1020 ms 64108 KB Output is correct
62 Correct 27 ms 32092 KB Output is correct
63 Correct 1221 ms 68104 KB Output is correct
64 Correct 730 ms 64748 KB Output is correct
65 Correct 987 ms 66592 KB Output is correct
66 Correct 1147 ms 67288 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 68876 KB Output is correct
2 Correct 624 ms 70804 KB Output is correct
3 Correct 270 ms 60188 KB Output is correct
4 Correct 475 ms 65876 KB Output is correct
5 Correct 28 ms 32024 KB Output is correct
6 Correct 581 ms 68776 KB Output is correct
7 Correct 132 ms 44956 KB Output is correct
8 Correct 154 ms 47140 KB Output is correct
9 Correct 274 ms 59020 KB Output is correct
10 Correct 558 ms 69920 KB Output is correct
11 Correct 199 ms 54656 KB Output is correct
12 Correct 27 ms 31992 KB Output is correct
13 Correct 27 ms 31992 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 32064 KB Output is correct
16 Correct 28 ms 31992 KB Output is correct
17 Correct 27 ms 31992 KB Output is correct
18 Correct 27 ms 31992 KB Output is correct
19 Correct 27 ms 31992 KB Output is correct
20 Correct 28 ms 32036 KB Output is correct
21 Correct 28 ms 32092 KB Output is correct
22 Correct 28 ms 32084 KB Output is correct
23 Correct 27 ms 31992 KB Output is correct
24 Correct 27 ms 31992 KB Output is correct
25 Correct 27 ms 31992 KB Output is correct
26 Correct 27 ms 31972 KB Output is correct
27 Correct 27 ms 31992 KB Output is correct
28 Correct 30 ms 32464 KB Output is correct
29 Correct 31 ms 32432 KB Output is correct
30 Correct 34 ms 32492 KB Output is correct
31 Correct 32 ms 32376 KB Output is correct
32 Correct 33 ms 32412 KB Output is correct
33 Correct 33 ms 32376 KB Output is correct
34 Correct 34 ms 32448 KB Output is correct
35 Correct 493 ms 55992 KB Output is correct
36 Correct 541 ms 68820 KB Output is correct
37 Correct 491 ms 63172 KB Output is correct
38 Correct 551 ms 68764 KB Output is correct
39 Correct 507 ms 67716 KB Output is correct
40 Correct 247 ms 55940 KB Output is correct
41 Correct 1207 ms 70236 KB Output is correct
42 Correct 276 ms 57572 KB Output is correct
43 Correct 157 ms 47708 KB Output is correct
44 Correct 716 ms 67132 KB Output is correct
45 Correct 927 ms 69580 KB Output is correct
46 Correct 1143 ms 67460 KB Output is correct
47 Correct 1103 ms 66296 KB Output is correct
48 Correct 513 ms 63072 KB Output is correct
49 Correct 585 ms 67720 KB Output is correct
50 Correct 610 ms 69328 KB Output is correct
51 Correct 684 ms 65172 KB Output is correct
52 Correct 27 ms 31980 KB Output is correct
53 Correct 1217 ms 69304 KB Output is correct
54 Correct 737 ms 66060 KB Output is correct
55 Correct 923 ms 68348 KB Output is correct
56 Correct 1199 ms 69480 KB Output is correct
57 Correct 2654 ms 146320 KB Output is correct
58 Correct 3104 ms 166772 KB Output is correct
59 Correct 3151 ms 176308 KB Output is correct
60 Correct 3734 ms 159216 KB Output is correct
61 Incorrect 7634 ms 175472 KB Output isn't correct
62 Halted 0 ms 0 KB -