oj.uz

Submission #170777

# Submission time Handle Problem Language Result Execution time Memory
170777 2019-12-26T10:43:30 Z gs18103 Two Dishes (JOI19_dishes) C++14
49 / 100
 1186 ms 73728 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);
        int 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 707 ms 66356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32072 KB Output is correct
2 Correct 27 ms 31996 KB Output is correct
3 Correct 27 ms 31992 KB Output is correct
4 Correct 26 ms 32016 KB Output is correct
5 Correct 27 ms 31992 KB Output is correct
6 Correct 27 ms 31992 KB Output is correct
7 Correct 28 ms 31992 KB Output is correct
8 Correct 27 ms 32096 KB Output is correct
9 Correct 27 ms 31992 KB Output is correct
10 Correct 27 ms 31992 KB Output is correct
11 Correct 27 ms 32068 KB Output is correct
12 Correct 27 ms 32120 KB Output is correct
13 Correct 27 ms 32092 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 32008 KB Output is correct
16 Correct 26 ms 31992 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32072 KB Output is correct
2 Correct 27 ms 31996 KB Output is correct
3 Correct 27 ms 31992 KB Output is correct
4 Correct 26 ms 32016 KB Output is correct
5 Correct 27 ms 31992 KB Output is correct
6 Correct 27 ms 31992 KB Output is correct
7 Correct 28 ms 31992 KB Output is correct
8 Correct 27 ms 32096 KB Output is correct
9 Correct 27 ms 31992 KB Output is correct
10 Correct 27 ms 31992 KB Output is correct
11 Correct 27 ms 32068 KB Output is correct
12 Correct 27 ms 32120 KB Output is correct
13 Correct 27 ms 32092 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 32008 KB Output is correct
16 Correct 26 ms 31992 KB Output is correct
17 Correct 30 ms 32284 KB Output is correct
18 Correct 31 ms 32504 KB Output is correct
19 Correct 33 ms 32480 KB Output is correct
20 Correct 31 ms 32376 KB Output is correct
21 Correct 32 ms 32420 KB Output is correct
22 Correct 33 ms 32416 KB Output is correct
23 Correct 33 ms 32420 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32072 KB Output is correct
2 Correct 27 ms 31996 KB Output is correct
3 Correct 27 ms 31992 KB Output is correct
4 Correct 26 ms 32016 KB Output is correct
5 Correct 27 ms 31992 KB Output is correct
6 Correct 27 ms 31992 KB Output is correct
7 Correct 28 ms 31992 KB Output is correct
8 Correct 27 ms 32096 KB Output is correct
9 Correct 27 ms 31992 KB Output is correct
10 Correct 27 ms 31992 KB Output is correct
11 Correct 27 ms 32068 KB Output is correct
12 Correct 27 ms 32120 KB Output is correct
13 Correct 27 ms 32092 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 32008 KB Output is correct
16 Correct 26 ms 31992 KB Output is correct
17 Correct 30 ms 32284 KB Output is correct
18 Correct 31 ms 32504 KB Output is correct
19 Correct 33 ms 32480 KB Output is correct
20 Correct 31 ms 32376 KB Output is correct
21 Correct 32 ms 32420 KB Output is correct
22 Correct 33 ms 32416 KB Output is correct
23 Correct 33 ms 32420 KB Output is correct
24 Correct 492 ms 59396 KB Output is correct
25 Correct 536 ms 72328 KB Output is correct
26 Correct 483 ms 66720 KB Output is correct
27 Correct 557 ms 72496 KB Output is correct
28 Correct 518 ms 71264 KB Output is correct
29 Correct 253 ms 60036 KB Output is correct
30 Correct 1186 ms 73728 KB Output is correct
31 Correct 272 ms 57496 KB Output is correct
32 Correct 169 ms 47804 KB Output is correct
33 Correct 809 ms 70444 KB Output is correct
34 Correct 921 ms 72924 KB Output is correct
35 Correct 1139 ms 67484 KB Output is correct
36 Correct 1107 ms 67372 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32072 KB Output is correct
2 Correct 27 ms 31996 KB Output is correct
3 Correct 27 ms 31992 KB Output is correct
4 Correct 26 ms 32016 KB Output is correct
5 Correct 27 ms 31992 KB Output is correct
6 Correct 27 ms 31992 KB Output is correct
7 Correct 28 ms 31992 KB Output is correct
8 Correct 27 ms 32096 KB Output is correct
9 Correct 27 ms 31992 KB Output is correct
10 Correct 27 ms 31992 KB Output is correct
11 Correct 27 ms 32068 KB Output is correct
12 Correct 27 ms 32120 KB Output is correct
13 Correct 27 ms 32092 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 32008 KB Output is correct
16 Correct 26 ms 31992 KB Output is correct
17 Correct 30 ms 32284 KB Output is correct
18 Correct 31 ms 32504 KB Output is correct
19 Correct 33 ms 32480 KB Output is correct
20 Correct 31 ms 32376 KB Output is correct
21 Correct 32 ms 32420 KB Output is correct
22 Correct 33 ms 32416 KB Output is correct
23 Correct 33 ms 32420 KB Output is correct
24 Correct 492 ms 59396 KB Output is correct
25 Correct 536 ms 72328 KB Output is correct
26 Correct 483 ms 66720 KB Output is correct
27 Correct 557 ms 72496 KB Output is correct
28 Correct 518 ms 71264 KB Output is correct
29 Correct 253 ms 60036 KB Output is correct
30 Correct 1186 ms 73728 KB Output is correct
31 Correct 272 ms 57496 KB Output is correct
32 Correct 169 ms 47804 KB Output is correct
33 Correct 809 ms 70444 KB Output is correct
34 Correct 921 ms 72924 KB Output is correct
35 Correct 1139 ms 67484 KB Output is correct
36 Correct 1107 ms 67372 KB Output is correct
37 Incorrect 477 ms 69632 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32072 KB Output is correct
2 Correct 27 ms 31996 KB Output is correct
3 Correct 27 ms 31992 KB Output is correct
4 Correct 26 ms 32016 KB Output is correct
5 Correct 27 ms 31992 KB Output is correct
6 Correct 27 ms 31992 KB Output is correct
7 Correct 28 ms 31992 KB Output is correct
8 Correct 27 ms 32096 KB Output is correct
9 Correct 27 ms 31992 KB Output is correct
10 Correct 27 ms 31992 KB Output is correct
11 Correct 27 ms 32068 KB Output is correct
12 Correct 27 ms 32120 KB Output is correct
13 Correct 27 ms 32092 KB Output is correct
14 Correct 27 ms 31992 KB Output is correct
15 Correct 27 ms 32008 KB Output is correct
16 Correct 26 ms 31992 KB Output is correct
17 Correct 30 ms 32284 KB Output is correct
18 Correct 31 ms 32504 KB Output is correct
19 Correct 33 ms 32480 KB Output is correct
20 Correct 31 ms 32376 KB Output is correct
21 Correct 32 ms 32420 KB Output is correct
22 Correct 33 ms 32416 KB Output is correct
23 Correct 33 ms 32420 KB Output is correct
24 Correct 492 ms 59396 KB Output is correct
25 Correct 536 ms 72328 KB Output is correct
26 Correct 483 ms 66720 KB Output is correct
27 Correct 557 ms 72496 KB Output is correct
28 Correct 518 ms 71264 KB Output is correct
29 Correct 253 ms 60036 KB Output is correct
30 Correct 1186 ms 73728 KB Output is correct
31 Correct 272 ms 57496 KB Output is correct
32 Correct 169 ms 47804 KB Output is correct
33 Correct 809 ms 70444 KB Output is correct
34 Correct 921 ms 72924 KB Output is correct
35 Correct 1139 ms 67484 KB Output is correct
36 Correct 1107 ms 67372 KB Output is correct
37 Incorrect 477 ms 69632 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 707 ms 66356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 707 ms 66356 KB Output isn't correct
2 Halted 0 ms 0 KB -