oj.uz

Submission #781839

# Submission time Handle Problem Language Result Execution time Memory
781839 2023-07-13T11:50:52 Z TeaTime Two Dishes (JOI19_dishes) C++17
5 / 100
 800 ms 123468 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);
    }

    for (int i = 0; i < SZ; i++) {
        seg[i] = -INF;
    }

    upd(0, 0, SZ, 0, 0);

    // 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:171:12: warning: variable 'prev' set but not used [-Wunused-but-set-variable]
  171 |         ll prev = -1;
      |            ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 117188 KB Output is correct
2 Correct 650 ms 123468 KB Output is correct
3 Correct 794 ms 123448 KB Output is correct
4 Correct 382 ms 86656 KB Output is correct
5 Correct 17 ms 31700 KB Output is correct
6 Correct 726 ms 120080 KB Output is correct
7 Correct 339 ms 84524 KB Output is correct
8 Correct 429 ms 64984 KB Output is correct
9 Correct 800 ms 122976 KB Output is correct
10 Correct 515 ms 110760 KB Output is correct
11 Correct 746 ms 122872 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31700 KB Output is correct
2 Correct 17 ms 31700 KB Output is correct
3 Correct 22 ms 31684 KB Output is correct
4 Incorrect 18 ms 31696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31700 KB Output is correct
2 Correct 17 ms 31700 KB Output is correct
3 Correct 22 ms 31684 KB Output is correct
4 Incorrect 18 ms 31696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31700 KB Output is correct
2 Correct 17 ms 31700 KB Output is correct
3 Correct 22 ms 31684 KB Output is correct
4 Incorrect 18 ms 31696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31700 KB Output is correct
2 Correct 17 ms 31700 KB Output is correct
3 Correct 22 ms 31684 KB Output is correct
4 Incorrect 18 ms 31696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31700 KB Output is correct
2 Correct 17 ms 31700 KB Output is correct
3 Correct 22 ms 31684 KB Output is correct
4 Incorrect 18 ms 31696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 117188 KB Output is correct
2 Correct 650 ms 123468 KB Output is correct
3 Correct 794 ms 123448 KB Output is correct
4 Correct 382 ms 86656 KB Output is correct
5 Correct 17 ms 31700 KB Output is correct
6 Correct 726 ms 120080 KB Output is correct
7 Correct 339 ms 84524 KB Output is correct
8 Correct 429 ms 64984 KB Output is correct
9 Correct 800 ms 122976 KB Output is correct
10 Correct 515 ms 110760 KB Output is correct
11 Correct 746 ms 122872 KB Output is correct
12 Correct 17 ms 31700 KB Output is correct
13 Correct 17 ms 31700 KB Output is correct
14 Correct 22 ms 31684 KB Output is correct
15 Incorrect 18 ms 31696 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 117188 KB Output is correct
2 Correct 650 ms 123468 KB Output is correct
3 Correct 794 ms 123448 KB Output is correct
4 Correct 382 ms 86656 KB Output is correct
5 Correct 17 ms 31700 KB Output is correct
6 Correct 726 ms 120080 KB Output is correct
7 Correct 339 ms 84524 KB Output is correct
8 Correct 429 ms 64984 KB Output is correct
9 Correct 800 ms 122976 KB Output is correct
10 Correct 515 ms 110760 KB Output is correct
11 Correct 746 ms 122872 KB Output is correct
12 Correct 17 ms 31700 KB Output is correct
13 Correct 17 ms 31700 KB Output is correct
14 Correct 22 ms 31684 KB Output is correct
15 Incorrect 18 ms 31696 KB Output isn't correct
16 Halted 0 ms 0 KB -