Submission #1094215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094215		8pete8	Two Dishes (JOI19_dishes)	C++17	100 / 100	3558 ms	183172 KiB

dishes

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include<queue>
#include<cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<iomanip>
#include<numeric>
#include<bitset>
using namespace std;

#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#define int long long
#define double long double

using namespace std;

const int mod = 998244353, mxn = 1e6+5, inf = 1e16, minf = -1e16, lg = 30;
//#undef int

int n, k, m, q;

void setIO(string name) {
    ios_base::sync_with_stdio(0); 
    cin.tie(0);		
    freopen((name + ".in").c_str(), "r", stdin);		
    freopen((name + ".out").c_str(), "w", stdout);	
}

pair<int,pii> v1[mxn+10], v2[mxn+10];

//time,before,point
struct seg {
    int v[4*mxn+10], lazy1[4*mxn+10], lazy2[4*mxn+10];

    void build(int l, int r, int pos) {
        int mid = l + (r - l) / 2;
        lazy2[pos] = minf;
        if (l == r) return;
        build(l, mid, pos * 2);
        build(mid + 1, r, pos * 2 + 1);
    }

    void push(int l, int r, int pos) {
        v[pos] = max(v[pos] + lazy1[pos], lazy2[pos]);
        if (l != r) {
            if (lazy2[pos * 2] != minf) lazy2[pos * 2] += lazy1[pos];
            if (lazy2[pos * 2 + 1] != minf) lazy2[pos * 2 + 1] += lazy1[pos];
            lazy1[pos * 2 + 1] += lazy1[pos];
            lazy1[pos * 2] += lazy1[pos];
            lazy2[pos * 2] = max(lazy2[pos * 2], lazy2[pos]);
            lazy2[pos * 2 + 1] = max(lazy2[pos * 2 + 1], lazy2[pos]);
        }

        lazy2[pos] = minf;
        lazy1[pos] = 0;
    }

    void updateadd(int l, int r, int ql, int qr, int val, int pos) {
        push(l, r, pos);
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            lazy1[pos] += val;
            push(l, r, pos);
            return;
        }
        int mid = l + (r - l) / 2;
        updateadd(l, mid, ql, qr, val, pos * 2);
        updateadd(mid + 1, r, ql, qr, val, pos * 2 + 1);
        v[pos] = max(v[pos * 2], v[pos * 2 + 1]);
    }

    void updateset(int l, int r, int ql, int qr, int val, int pos) {
        push(l, r, pos);
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            lazy2[pos] = max(lazy2[pos], val);
            push(l, r, pos);
            return;
        }
        int mid = l + (r - l) / 2;
        updateset(l, mid, ql, qr, val, pos * 2);
        updateset(mid + 1, r, ql, qr, val, pos * 2 + 1);
        v[pos] = max(v[pos * 2], v[pos * 2 + 1]);
    }

    int qry(int l, int r, int qpos, int pos) {
        push(l, r, pos);
        if (l == r) return v[pos];
        int mid = l + (r - l) / 2;
        if (qpos <= mid) return qry(l, mid, qpos, pos * 2);
        return qry(mid + 1, r, qpos, pos * 2 + 1);
    }
} t;

int getbound(int x, int add) {
    int l = 0, r = n, pos = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (v1[mid].f + add <= x) l = mid + 1, pos = max(pos, mid);
        else r = mid - 1;
    }
    return pos;
}

int32_t main() {
    fastio
    //n^2 can use lazy seg to op
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v1[i].f >> v1[i].s.f >> v1[i].s.s;
        v1[i].f += v1[i-1].f;
    }
    for (int i = 1; i <= m; i++) {
        cin >> v2[i].f >> v2[i].s.f >> v2[i].s.s;
        v2[i].f += v2[i-1].f;
    }
    int ans1 = 0;
    vector<pii> gap;
    for (int i = 1; i <= n; i++) {
        if (v1[i].f <= v1[i].s.f) {
            gap.pb({v1[i].s.f - v1[i].f, i});
            ans1 += v1[i].s.s;
        }
    }
    t.build(0, n, 1);
    sort(all(gap));
    int cur = 0, bruh, where, x;
    vector<int32_t> cut;
    for (int j = 1; j <= m; j++) {
        while (cur < gap.size() && gap[cur].f < v2[j].f) {
            t.updateadd(0, n, 0, gap[cur].s - 1, -v1[gap[cur].s].s.s, 1);
            if (v1[gap[cur].s].s.s < 0) cut.pb(gap[cur].s - 1);
            cur++;
        }
        x = getbound(v2[j].s.f, v2[j].f);
        if (x != -1) {
            cut.pb(x);
            t.updateadd(0, n, 0, x, v2[j].s.s, 1);
            if (v2[j].s.s > 0) cut.pb(x);
        }
        for (auto i : cut) {
            bruh = t.qry(0, n, i, 1);
            t.updateset(0, n, i + 1, n, bruh, 1);
        }
        cut.clear();
    }
    t.push(0, n, 1);
    cout << ans1 + t.v[1] << '\n';
}

/*
 
*/

Compilation message (stderr)

dishes.cpp: In function 'int32_t main()':
dishes.cpp:152:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         while (cur < gap.size() && gap[cur].f < v2[j].f) {
      |                ~~~~^~~~~~~~~~~~
dishes.cpp:149:24: warning: unused variable 'where' [-Wunused-variable]
  149 |     int cur = 0, bruh, where, x;
      |                        ^~~~~
dishes.cpp: In function 'void setIO(std::string)':
dishes.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen((name + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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