Submission #623700

#TimeUsernameProblemLanguageResultExecution timeMemory
623700Loki_NguyenTwo Dishes (JOI19_dishes)C++14
0 / 100
322 ms98316 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define task "dfss" #define pll pair<int, ll> #define pii pair<int, int> #define fi first #define se second #define ull unsigned long long using namespace std; const ll mod = 998244353; const ll N = 2e6 + 55; const ll inf = 1e18; vector<pll> adj[N]; ll pw(ll k, ll n) { ll total = 1; for (; n; n >>= 1) { if (n & 1) total = total * k % mod; k = k * k % mod; } return total; } struct node { ll x, s, p; } a[N], b[N]; struct IT { vector<ll> st, lazy, lmx; int n; IT(int _n) { n = _n; st.resize(n * 4 + 4, 0); lazy.resize(n * 4 + 4, 0); lmx.resize(n * 4 + 4, -inf); } void down(int id) { if (lazy[id] != 0) { st[id << 1 | 1] += lazy[id]; st[id << 1] += lazy[id]; lazy[id << 1] += lazy[id]; lazy[id << 1 | 1] += lazy[id]; lazy[id] = 0; } if (lmx[id] != -inf) { lmx[id << 1] = max(lmx[id << 1], lmx[id]); lmx[id << 1 | 1] = max(lmx[id << 1 | 1], lmx[id]); st[id << 1] = max(st[id << 1], lmx[id]); st[id << 1 | 1] = max(st[id << 1 | 1], lmx[id]); lmx[id] = -inf; } } void update(int id, int l, int r, int u, int v, ll x) { if (u <= l && r <= v) { st[id] += x; lazy[id] += x; return; } if (u > r || l > v) return; int mid = (l + r) >> 1; down(id); update(id << 1, l, mid, u, v, x); update(id << 1 | 1, mid + 1, r, u, v, x); st[id] = max(st[id << 1 | 1], st[id << 1]); } void update(int l, int r, ll x) { update(1, 0, n, l, r, x); } void upd(int id, int l, int r, int u, int v, ll x) { if (u <= l && r <= v) { st[id] = max(st[id], x); lmx[id] = (lmx[id], x); return; } if (u > r || l > v) return; int mid = (l + r) >> 1; down(id); upd(id << 1, l, mid, u, v, x); upd(id << 1 | 1, mid + 1, r, u, v, x); st[id] = max(st[id << 1 | 1], st[id << 1]); } void upd(int l, int r, ll x) { upd(1, 0, n, l, r, x); } ll get(int id, int l, int r, int pos) { if (l == r) return st[id]; int mid = (l + r) >> 1; down(id); if (pos <= mid) return get(id << 1, l, mid, pos); return get(id << 1 | 1, mid + 1, r, pos); } ll get(int pos) { return get(1, 0, n, pos); } }; int n, m, t, k; ll ans, c[N], sum; void sol() { cin >> n >> m; a[0].x = 0; b[0].x = 0; for (int i = 1; i <= n; i++) { cin >> a[i].x >> a[i].s >> a[i].p; a[i].x += a[i - 1].x; } for (int i = 1; i <= m; i++) { cin >> b[i].x >> b[i].s >> b[i].p; b[i].x += b[i - 1].x; int l = 1, r = n, mid; while (l <= r) { mid = (l + r) >> 1; if (a[mid].x + b[i].x <= b[i].s) l = mid + 1; else r = mid - 1; } if (a[r].x + b[i].x <= b[i].s) { ans += b[i].p; if (r < n) { //cout << r + 1 << " " << i - 1 << " " << -b[i].p << '\n'; adj[r + 1].pb({i - 1, -b[i].p}); } } } IT it(m); for (int i = 1; i <= n; i++) { int l = 1, r = m, mid; while (l <= r) { mid = (l + r) >> 1; if (b[mid].x + a[i].x <= a[i].s) l = mid + 1; else r = mid - 1; } if (b[r].x + a[i].x <= a[i].s) { adj[i].pb({r, a[i].p}); //cout << i << " " << r << " " << a[i].p << '\n'; } sort(adj[i].begin(), adj[i].end()); k = adj[i].size(); for (int j = 0; j < k;) { int pos = adj[i][j].fi; sum = 0; while (j < k && adj[i][j].fi == pos) { sum += adj[i][j].se; ++j; } //cout << i << " " << pos << " " << sum << ' '; it.update(0, pos, sum); it.upd(pos, (j == k ? m: adj[i][j].fi), it.get(pos)); // cout << it.get(m) <<'\n'; } } cout << ans +it.get(m); } int main() { if (fopen(task ".inp", "r")) { freopen(task ".inp", "r", stdin); freopen(task ".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ntest = 1; // cout << (1<<20); // cin >> ntest; while (ntest-- > 0) sol(); } /* */

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:192:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:193:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...