oj.uz

Submission #781837

# Submission time Handle Problem Language Result Execution time Memory
781837 2023-07-13T11:47:40 Z TeaTime Two Dishes (JOI19_dishes) C++17
5 / 100
 871 ms 131060 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;
typedef long double ld;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 1'000'100, INF = 2'000'000'000'000'000'000;

ll n, m;

struct el {
    ll a, s, p;
};

vector<el> vec1, vec2;
vector<ll> pref1, pref2;

struct point {
    ll x, y, val;
};

vector<point> blue, red;

ll seg[SZ * 8], psh[SZ * 8];

void push(int v) {
    seg[v * 2 + 1] += psh[v];
    seg[v * 2 + 2] += psh[v];

    psh[v * 2 + 1] += psh[v];
    psh[v * 2 + 2] += psh[v];

    psh[v] = 0;
}

void upd(int v, int l, int r, int askl, int askr, ll val) {
    push(v);
    if (l >= askr || r <= askl) return;

    if (askl <= l && r <= askr) {
        seg[v] += val;
        psh[v] += val;
        return;
    }

    int mid = (l + r) / 2;
    upd(v * 2 + 1, l, mid, askl, askr, val);
    upd(v * 2 + 2, mid, r, askl, askr, val);
    seg[v] = max(seg[v * 2 + 1], seg[v * 2 + 2]);
}

void upd(int v, int l, int r, int pos, ll val) {
    push(v);
    if (l == r - 1) {
        seg[v] = val;
    } else {
        int mid = (l + r) / 2;

        if (pos < mid) {
            upd(v * 2 + 1, l, mid, pos, val);
        } else {
            upd(v * 2 + 2, mid, r, pos, val);
        }

        seg[v] = max(seg[v * 2 + 1], seg[v * 2 + 2]);
    }
}

ll ask(int v, int l, int r, int askl, int askr) {
    push(v);
    if (l >= askr || r <= askl) return -INF;

    if (askl <= l && r <= askr) return seg[v];

    int mid = (l + r) / 2;
    return max(ask(v * 2 + 1, l, mid, askl, askr), ask(v * 2 + 2, mid, r, askl, askr));
}

vector<point> points[SZ];

bool cmp(point a, point b) {
    return a.y < b.y;
}

int main() {
    fastInp;

    cin >> n >> m;

    vec1.resize(n);
    vec2.resize(m);

    pref1.push_back(0);
    for (auto &c : vec1) {
        cin >> c.a >> c.s >> c.p;
        pref1.push_back(pref1.back() + c.a);
    }

    pref2.push_back(0);
    for (auto &c : vec2) {
        cin >> c.a >> c.s >> c.p;
        pref2.push_back(pref2.back() + c.a);
    }

    // x is vec1
    // y is vec2
    ll ans = 0, prefsum = 0;
    for (int i = 0; i < n; i++) {
        prefsum += vec1[i].a;

        ll left = vec1[i].s - prefsum;
        if (left < 0) continue;

        int ind = upper_bound(pref2.begin(), pref2.end(), left) - pref2.begin() - 1;
        assert(ind >= 0);

        blue.push_back({i + 1, ind, vec1[i].p}); // above or on the lattice path
    }

    prefsum = 0;

    for (int i = 0; i < m; i++) {
        prefsum += vec2[i].a;

        ll left = vec2[i].s - prefsum;
        if (left < 0) continue;

        int ind = upper_bound(pref1.begin(), pref1.end(), left) - pref1.begin() - 1;
        assert(ind >= 0);

        red.push_back({ind, i + 1, vec2[i].p}); // under or on the lattice path
        blue.push_back({ind + 1, i, -vec2[i].p}); // above or on the lattice path
        ans += vec2[i].p;
    }

    for (auto c : blue) {
        points[c.x].push_back(c);
        if (c.x != 0) points[c.x - 1].push_back({c.x - 1, c.y - 1, 0});
        if (c.x != 0) points[c.x - 1].push_back({c.x - 1, c.y + 1, 0});
        if (c.x != 0) points[c.x - 1].push_back({c.x - 1, c.y, 0});
    }

    for (int i = 0; i < SZ; i++) {
        sort(points[i].begin(), points[i].end(), cmp);

        vector<point> cur;
        for (auto c : points[i]) {
            if (!cur.empty() && cur.back().y == c.y) {
                cur.back().val += c.val;
            } else {
                cur.push_back(c);
            }
        }

        points[i] = cur;

        ll prev = -1;

        for (auto c : points[i]) {
            upd(0, 0, SZ, 0, c.y + 1, c.val);
            ll q = ask(0, 0, SZ, 0, c.y + 1);
            upd(0, 0, SZ, c.y, q);
            prev = c.y;
        }
    }

    cout << ans + ask(0, 0, SZ, 0, SZ);

    return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:165:12: warning: variable 'prev' set but not used [-Wunused-but-set-variable]
  165 |         ll prev = -1;
      |            ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 123500 KB Output is correct
2 Correct 692 ms 130456 KB Output is correct
3 Correct 871 ms 130144 KB Output is correct
4 Correct 396 ms 93056 KB Output is correct
5 Correct 17 ms 23924 KB Output is correct
6 Correct 736 ms 127028 KB Output is correct
7 Correct 372 ms 84604 KB Output is correct
8 Correct 443 ms 63828 KB Output is correct
9 Correct 867 ms 131060 KB Output is correct
10 Correct 606 ms 111856 KB Output is correct
11 Correct 779 ms 124516 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 18 ms 23812 KB Output is correct
3 Correct 16 ms 23944 KB Output is correct
4 Incorrect 16 ms 23864 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 18 ms 23812 KB Output is correct
3 Correct 16 ms 23944 KB Output is correct
4 Incorrect 16 ms 23864 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 18 ms 23812 KB Output is correct
3 Correct 16 ms 23944 KB Output is correct
4 Incorrect 16 ms 23864 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 18 ms 23812 KB Output is correct
3 Correct 16 ms 23944 KB Output is correct
4 Incorrect 16 ms 23864 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 18 ms 23812 KB Output is correct
3 Correct 16 ms 23944 KB Output is correct
4 Incorrect 16 ms 23864 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 123500 KB Output is correct
2 Correct 692 ms 130456 KB Output is correct
3 Correct 871 ms 130144 KB Output is correct
4 Correct 396 ms 93056 KB Output is correct
5 Correct 17 ms 23924 KB Output is correct
6 Correct 736 ms 127028 KB Output is correct
7 Correct 372 ms 84604 KB Output is correct
8 Correct 443 ms 63828 KB Output is correct
9 Correct 867 ms 131060 KB Output is correct
10 Correct 606 ms 111856 KB Output is correct
11 Correct 779 ms 124516 KB Output is correct
12 Correct 16 ms 23892 KB Output is correct
13 Correct 18 ms 23812 KB Output is correct
14 Correct 16 ms 23944 KB Output is correct
15 Incorrect 16 ms 23864 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 123500 KB Output is correct
2 Correct 692 ms 130456 KB Output is correct
3 Correct 871 ms 130144 KB Output is correct
4 Correct 396 ms 93056 KB Output is correct
5 Correct 17 ms 23924 KB Output is correct
6 Correct 736 ms 127028 KB Output is correct
7 Correct 372 ms 84604 KB Output is correct
8 Correct 443 ms 63828 KB Output is correct
9 Correct 867 ms 131060 KB Output is correct
10 Correct 606 ms 111856 KB Output is correct
11 Correct 779 ms 124516 KB Output is correct
12 Correct 16 ms 23892 KB Output is correct
13 Correct 18 ms 23812 KB Output is correct
14 Correct 16 ms 23944 KB Output is correct
15 Incorrect 16 ms 23864 KB Output isn't correct
16 Halted 0 ms 0 KB -