Submission #623016

#	Time	Username	Problem	Language	Result	Execution time	Memory
623016		Joshc	Two Dishes (JOI19_dishes)	C++11	100 / 100	4222 ms	352080 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
const int MAX_N = 2e6+5;
 
struct line {
    ll x, y, val;
};
 
bool comp(line a, line b) {
    if (a.x != b.x) return a.x < b.x;
    if (a.y != b.y) return a.y > b.y;
    return a.val < b.val;
}
 
struct node {
    ll val = 0, add = 0, mx = -1e16;
};
vector<node> seg(4*MAX_N);
 
void push(int v) {
    seg[v<<1].add += seg[v].add;
    seg[v<<1].mx = max(seg[v<<1].mx+seg[v].add, seg[v].mx);
    seg[v<<1].val = max(seg[v<<1].val+seg[v].add, seg[v].mx);
    seg[v<<1|1].add += seg[v].add;
    seg[v<<1|1].mx = max(seg[v<<1|1].mx+seg[v].add, seg[v].mx);
    seg[v<<1|1].val = max(seg[v<<1|1].val+seg[v].add, seg[v].mx);
    seg[v].add = 0;
    seg[v].mx = -1e16;
}
 
void update(int v, int tl, int tr, int l, int r, ll add, ll mx) {
    if (l > r) return;
    if (l == tl && r == tr) {
        seg[v].val = max(seg[v].val+add, mx);
        seg[v].add += add;
        seg[v].mx = max(seg[v].mx+add, mx);
    } else {
        int tm = (tl+tr) >> 1;
        push(v);
        update(v<<1, tl, tm, l, min(r, tm), add, mx);
        update(v<<1|1, tm+1, tr, max(l, tm+1), r, add, mx);
        seg[v].val = max(seg[v<<1].val, seg[v<<1|1].val);
    }
}
 
ll query(int v, int tl, int tr, int l, int r) {
    if (l > r) return -1e16;
    if (l == tl && r == tr) return seg[v].val;
    int tm = (tl+tr) >> 1;
    push(v);
    return max(query(v<<1, tl, tm, l, min(r, tm)), query(v<<1|1, tm+1, tr, max(l, tm+1), r));
}
 
ll a[MAX_N], b[MAX_N], p[MAX_N], q[MAX_N], s[MAX_N], t[MAX_N];
vector<line> ranges; 
 
int main() {
    int n, m;
    ll ans = 0;
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) {
        scanf("%lld%lld%lld", &a[i], &s[i], &p[i]);
        a[i] += a[i-1];
    }
    for (int i=1; i<=m; i++) {
        scanf("%lld%lld%lld", &b[i], &t[i], &q[i]);
        b[i] += b[i-1];
    }
    for (int i=1; i<=n; i++) {
        if (a[i] > s[i]) continue;
        int low = 0, high = m, mid;
        while (low != high) {
            mid = (low+high+1) >> 1;
            if (a[i]+b[mid] <= s[i]) low = mid;
            else high = mid-1;
        }
        if (low < m) ranges.push_back(line{i, low+1, p[i]});
        else ans += p[i];
    }
    for (int i=1; i<=m; i++) {
        if (b[i] > t[i]) continue;
        int low = 0, high = n, mid;
        while (low != high) {
            mid = (low+high+1) >> 1;
            if (b[i]+a[mid] <= t[i]) low = mid;
            else high = mid-1;
        }
        ans += q[i];
        if (low < n) ranges.push_back(line{low+1, i, -q[i]});
    }
    sort(ranges.begin(), ranges.end(), comp);
    for (auto r : ranges) {
        update(1, 1, 2000001, 1, r.y, r.val, -1e16);
        ll cur = query(1, 1, 2000001, 1, r.y);
        update(1, 1, 2000001, r.y+1, 2000001, 0, cur);
    }
    printf("%lld\n", ans+seg[1].val);
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%lld%lld%lld", &a[i], &s[i], &p[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%lld%lld%lld", &b[i], &t[i], &q[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9