oj.uz

Submission #974522

# Submission time Handle Problem Language Result Execution time Memory
974522 2024-05-03T12:16:37 Z DAleksa Two Dishes (JOI19_dishes) C++17
8 / 100
 452 ms 196368 KB 
#include <bits/stdc++.h>

using namespace std;

struct node {
    long long mx;
    long long add;
    long long set;
    bool both;
    node() {
        mx = 0;
        add = 0;
        set = 0;
        both = false;
    }
};

struct pt {
    int y;
    long long val;
};

const int N = 1e6 + 10;
const long long inf = 1e18;
int n, m;
long long a[N], p[N], b[N], q[N];
long long s[N], t[N];
int x[N], y[N];
vector<pt> all[N];
node st[4 * N];

void propagate(int index) {
    if(2 * index + 1 < 4 * N) {
        if(st[index].both) {
            long long val = st[index].set + st[index].add;
            st[2 * index].mx = val;
            st[2 * index].set = val;
            st[2 * index].both = true;
            st[2 * index + 1].mx = val;
            st[2 * index + 1].set = val;
            st[2 * index + 1].both = true;
            st[index].add = 0;
            st[index].set = 0;
            st[index].both = false;
        } else {
            st[2 * index].mx += st[index].add;
            st[2 * index].add += st[index].add;
            st[2 * index + 1].mx += st[index].add;
            st[2 * index + 1].add += st[index].add;
            st[index].add = 0;
        }
    }
}

void update(int index, int l, int r, int L, int R, long long val) {
    if(l > r || r < L || R < l) return;
    if(L <= l && r <= R) {
        st[index].mx += val;
        st[index].add += val;
        return;
    }
    propagate(index);
    int mid = (l + r) / 2;
    update(2 * index, l, mid, L, R, val);
    update(2 * index + 1, mid + 1, r, L, R, val);
    st[index].mx = max(st[2 * index].mx, st[2 * index + 1].mx);
}

void modify(int index, int l, int r, int L, int R, long long val) {
    if(l > r || r < L || R < l) return;
    if(L <= l && r <= R) {
        st[index].mx = val;
        st[index].set = val;
        st[index].both = true;
        st[index].add = 0;
        return;
    }
    propagate(index);
    int mid = (l + r) / 2;
    modify(2 * index, l, mid, L, R, val);
    modify(2 * index + 1, mid + 1, r, L, R, val);
    st[index].mx = max(st[2 * index].mx, st[2 * index + 1].mx);
}

long long get(int index, int l, int r, int x) {
    if(l > r || r < x || x < l) return -inf;
    if(l == r) return st[index].mx;
    propagate(index);
    int mid = (l + r) / 2;
    return max(get(2 * index, l, mid, x), get(2 * index + 1, mid + 1, r, x));
}

int walk(int index, int l, int r, int x, long long val) {
    if(l > r || r < x) return r;
    if(l == r) {
        if(st[index].mx >= val) return l - 1;
        return l;
    }
    if(st[index].mx < val) return r;
    propagate(index);
    int mid = (l + r) / 2;
    int L = walk(2 * index, l, mid, x, val);
    if(L != mid) return L;
    return walk(2 * index + 1, mid + 1, r, x, val);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i] >> s[i] >> p[i];
    for(int i = 1; i <= m; i++) cin >> b[i] >> t[i] >> q[i];
    a[0] = b[0] = 0;
    for(int i = 2; i <= n; i++) a[i] += a[i - 1];
    for(int i = 2; i <= m; i++) b[i] += b[i - 1];
    for(int i = 1; i <= n; i++) {
        if(a[i] > s[i]) {
            x[i] = -1;
            continue;
        }
        int l = 0, r = m;
        int ans = l;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(a[i] + b[mid] <= s[i]) {
                ans = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        x[i] = ans;
    }
    for(int i = 1; i <= m; i++) {
        if(b[i] > t[i]) {
            y[i] = -1;
            continue;
        }
        int l = 0, r = n;
        int ans = l;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(a[mid] + b[i] <= t[i]) {
                ans = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        y[i] = ans;
    }
    long long add = 0;
    for(int i = 1; i <= n; i++) {
        if(x[i] == -1) continue;
        add += p[i];
        if(x[i] < m) all[x[i] + 1].push_back({i - 1, -p[i]});
    }
    for(int i = 1; i <= m; i++) {
        if(y[i] == -1) continue;
        all[i].push_back({y[i], q[i]});
    }
    for(int i = 1; i <= m; i++) {
        sort(all[i].begin(), all[i].end(), [&](pt p1, pt p2) {
            return p1.y > p2.y;
        });
    }
    // modify(1, 0, n, 1, n, 39);
    // for(int i = 0; i <= n; i++) cout << get(1, 0, n, i) << " ";
    // return 0;
    // cout << "POINTS:\n";
    // for(int i = 0; i <= m; i++) {
    //     for(pt p : all[i]) cout << i << " " << p.y << " " << p.val << "\n";
    // }
    for(int i = 0; i <= m; i++) {
        // cout << "#" << i << ":\nPOINTS:\n";
        for(pt p : all[i]) {
            int y = p.y;
            long long val = p.val;
            // cout << y << " " << val << "\n";
            update(1, 0, n, 0, y, val);
            long long mx = get(1, 0, n, y);
            int nxt = walk(1, 0, n, y + 1, mx);
            // cout << mx << " " << nxt << "\n";
            modify(1, 0, n, y, nxt, mx);
            // cout << "TREE:\n";
            // for(int j = 0; j <= n; j++) cout << get(1, 0, n, j) << " ";
            // cout << "\n";
        }
        // cout << "\n";
    }
    // for(int i = 1; i <= m; i++) {
    //     for(pt p : all[i]) cout << i << " " << p.y << " " << p.val << "\n";
    // }
    // for(int i = 1; i <= n; i++) cout << x[i] << " ";
    // cout << "\n";
    // for(int i = 1; i <= m; i++) cout << y[i] << " ";
    // cout << "\n";
    // cout << add << "\n";
    cout << get(1, 0, n, n) + add;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 195820 KB Output is correct
2 Correct 399 ms 196368 KB Output is correct
3 Correct 196 ms 192596 KB Output is correct
4 Correct 298 ms 192672 KB Output is correct
5 Correct 27 ms 164752 KB Output is correct
6 Correct 350 ms 195156 KB Output is correct
7 Correct 89 ms 181268 KB Output is correct
8 Correct 77 ms 175632 KB Output is correct
9 Correct 203 ms 193424 KB Output is correct
10 Correct 385 ms 189776 KB Output is correct
11 Correct 175 ms 186960 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 164544 KB Output is correct
2 Correct 26 ms 164688 KB Output is correct
3 Correct 25 ms 164692 KB Output is correct
4 Correct 26 ms 164688 KB Output is correct
5 Correct 29 ms 164688 KB Output is correct
6 Correct 26 ms 164700 KB Output is correct
7 Correct 26 ms 164700 KB Output is correct
8 Correct 27 ms 164696 KB Output is correct
9 Correct 26 ms 164764 KB Output is correct
10 Correct 26 ms 164700 KB Output is correct
11 Correct 27 ms 164568 KB Output is correct
12 Correct 26 ms 164688 KB Output is correct
13 Correct 26 ms 164760 KB Output is correct
14 Correct 25 ms 164684 KB Output is correct
15 Correct 27 ms 164692 KB Output is correct
16 Correct 26 ms 164692 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 164544 KB Output is correct
2 Correct 26 ms 164688 KB Output is correct
3 Correct 25 ms 164692 KB Output is correct
4 Correct 26 ms 164688 KB Output is correct
5 Correct 29 ms 164688 KB Output is correct
6 Correct 26 ms 164700 KB Output is correct
7 Correct 26 ms 164700 KB Output is correct
8 Correct 27 ms 164696 KB Output is correct
9 Correct 26 ms 164764 KB Output is correct
10 Correct 26 ms 164700 KB Output is correct
11 Correct 27 ms 164568 KB Output is correct
12 Correct 26 ms 164688 KB Output is correct
13 Correct 26 ms 164760 KB Output is correct
14 Correct 25 ms 164684 KB Output is correct
15 Correct 27 ms 164692 KB Output is correct
16 Correct 26 ms 164692 KB Output is correct
17 Correct 28 ms 164696 KB Output is correct
18 Correct 27 ms 164700 KB Output is correct
19 Incorrect 30 ms 164944 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 164544 KB Output is correct
2 Correct 26 ms 164688 KB Output is correct
3 Correct 25 ms 164692 KB Output is correct
4 Correct 26 ms 164688 KB Output is correct
5 Correct 29 ms 164688 KB Output is correct
6 Correct 26 ms 164700 KB Output is correct
7 Correct 26 ms 164700 KB Output is correct
8 Correct 27 ms 164696 KB Output is correct
9 Correct 26 ms 164764 KB Output is correct
10 Correct 26 ms 164700 KB Output is correct
11 Correct 27 ms 164568 KB Output is correct
12 Correct 26 ms 164688 KB Output is correct
13 Correct 26 ms 164760 KB Output is correct
14 Correct 25 ms 164684 KB Output is correct
15 Correct 27 ms 164692 KB Output is correct
16 Correct 26 ms 164692 KB Output is correct
17 Correct 28 ms 164696 KB Output is correct
18 Correct 27 ms 164700 KB Output is correct
19 Incorrect 30 ms 164944 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 164544 KB Output is correct
2 Correct 26 ms 164688 KB Output is correct
3 Correct 25 ms 164692 KB Output is correct
4 Correct 26 ms 164688 KB Output is correct
5 Correct 29 ms 164688 KB Output is correct
6 Correct 26 ms 164700 KB Output is correct
7 Correct 26 ms 164700 KB Output is correct
8 Correct 27 ms 164696 KB Output is correct
9 Correct 26 ms 164764 KB Output is correct
10 Correct 26 ms 164700 KB Output is correct
11 Correct 27 ms 164568 KB Output is correct
12 Correct 26 ms 164688 KB Output is correct
13 Correct 26 ms 164760 KB Output is correct
14 Correct 25 ms 164684 KB Output is correct
15 Correct 27 ms 164692 KB Output is correct
16 Correct 26 ms 164692 KB Output is correct
17 Correct 28 ms 164696 KB Output is correct
18 Correct 27 ms 164700 KB Output is correct
19 Incorrect 30 ms 164944 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 164544 KB Output is correct
2 Correct 26 ms 164688 KB Output is correct
3 Correct 25 ms 164692 KB Output is correct
4 Correct 26 ms 164688 KB Output is correct
5 Correct 29 ms 164688 KB Output is correct
6 Correct 26 ms 164700 KB Output is correct
7 Correct 26 ms 164700 KB Output is correct
8 Correct 27 ms 164696 KB Output is correct
9 Correct 26 ms 164764 KB Output is correct
10 Correct 26 ms 164700 KB Output is correct
11 Correct 27 ms 164568 KB Output is correct
12 Correct 26 ms 164688 KB Output is correct
13 Correct 26 ms 164760 KB Output is correct
14 Correct 25 ms 164684 KB Output is correct
15 Correct 27 ms 164692 KB Output is correct
16 Correct 26 ms 164692 KB Output is correct
17 Correct 28 ms 164696 KB Output is correct
18 Correct 27 ms 164700 KB Output is correct
19 Incorrect 30 ms 164944 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 195820 KB Output is correct
2 Correct 399 ms 196368 KB Output is correct
3 Correct 196 ms 192596 KB Output is correct
4 Correct 298 ms 192672 KB Output is correct
5 Correct 27 ms 164752 KB Output is correct
6 Correct 350 ms 195156 KB Output is correct
7 Correct 89 ms 181268 KB Output is correct
8 Correct 77 ms 175632 KB Output is correct
9 Correct 203 ms 193424 KB Output is correct
10 Correct 385 ms 189776 KB Output is correct
11 Correct 175 ms 186960 KB Output is correct
12 Correct 26 ms 164544 KB Output is correct
13 Correct 26 ms 164688 KB Output is correct
14 Correct 25 ms 164692 KB Output is correct
15 Correct 26 ms 164688 KB Output is correct
16 Correct 29 ms 164688 KB Output is correct
17 Correct 26 ms 164700 KB Output is correct
18 Correct 26 ms 164700 KB Output is correct
19 Correct 27 ms 164696 KB Output is correct
20 Correct 26 ms 164764 KB Output is correct
21 Correct 26 ms 164700 KB Output is correct
22 Correct 27 ms 164568 KB Output is correct
23 Correct 26 ms 164688 KB Output is correct
24 Correct 26 ms 164760 KB Output is correct
25 Correct 25 ms 164684 KB Output is correct
26 Correct 27 ms 164692 KB Output is correct
27 Correct 26 ms 164692 KB Output is correct
28 Correct 28 ms 164696 KB Output is correct
29 Correct 27 ms 164700 KB Output is correct
30 Incorrect 30 ms 164944 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 195820 KB Output is correct
2 Correct 399 ms 196368 KB Output is correct
3 Correct 196 ms 192596 KB Output is correct
4 Correct 298 ms 192672 KB Output is correct
5 Correct 27 ms 164752 KB Output is correct
6 Correct 350 ms 195156 KB Output is correct
7 Correct 89 ms 181268 KB Output is correct
8 Correct 77 ms 175632 KB Output is correct
9 Correct 203 ms 193424 KB Output is correct
10 Correct 385 ms 189776 KB Output is correct
11 Correct 175 ms 186960 KB Output is correct
12 Correct 26 ms 164544 KB Output is correct
13 Correct 26 ms 164688 KB Output is correct
14 Correct 25 ms 164692 KB Output is correct
15 Correct 26 ms 164688 KB Output is correct
16 Correct 29 ms 164688 KB Output is correct
17 Correct 26 ms 164700 KB Output is correct
18 Correct 26 ms 164700 KB Output is correct
19 Correct 27 ms 164696 KB Output is correct
20 Correct 26 ms 164764 KB Output is correct
21 Correct 26 ms 164700 KB Output is correct
22 Correct 27 ms 164568 KB Output is correct
23 Correct 26 ms 164688 KB Output is correct
24 Correct 26 ms 164760 KB Output is correct
25 Correct 25 ms 164684 KB Output is correct
26 Correct 27 ms 164692 KB Output is correct
27 Correct 26 ms 164692 KB Output is correct
28 Correct 28 ms 164696 KB Output is correct
29 Correct 27 ms 164700 KB Output is correct
30 Incorrect 30 ms 164944 KB Output isn't correct
31 Halted 0 ms 0 KB -