Submission #974416

#TimeUsernameProblemLanguageResultExecution timeMemory
974416DAleksaTwo Dishes (JOI19_dishes)C++17
0 / 100
518 ms179916 KiB
#include <bits/stdc++.h> using namespace std; struct node { long long mx; long long add; long long set; bool both; node() { mx = 0; add = 0; set = 0; both = false; } }; struct pt { int y; long long val; }; const int N = 1e6 + 10; const long long inf = 1e18; int n, m; long long a[N], p[N], b[N], q[N]; long long s[N], t[N]; int x[N], y[N]; vector<pt> all[N]; node st[4 * N]; void propagate(int index) { if(2 * index + 1 < 4 * N) { if(st[index].both) { long long val = st[index].set + st[index].add; st[2 * index].mx = val; st[2 * index].set = val; st[2 * index + 1].mx = val; st[2 * index + 1].set = val; st[index].add = 0; st[index].set = 0; st[index].both = false; } else { st[2 * index].mx += st[index].add; st[2 * index].add += st[index].add; st[2 * index + 1].mx += st[index].add; st[2 * index + 1].add += st[index].add; st[index].add = 0; } } } void update(int index, int l, int r, int L, int R, long long val) { if(l > r || r < L || R < l) return; if(L <= l && r <= R) { st[index].mx += val; st[index].add += val; return; } propagate(index); int mid = (l + r) / 2; update(2 * index, l, mid, L, R, val); update(2 * index + 1, mid + 1, r, L, R, val); st[index].mx = max(st[2 * index].mx, st[2 * index + 1].mx); } void modify(int index, int l, int r, int L, int R, long long val) { if(l > r || r < L || R < l) return; if(L <= l && r <= R) { st[index].mx = val; st[index].set = val; st[index].both = true; st[index].add = 0; return; } propagate(index); int mid = (l + r) / 2; modify(2 * index, l, mid, L, R, val); modify(2 * index + 1, mid + 1, r, L, R, val); st[index].mx = max(st[2 * index].mx, st[2 * index + 1].mx); } long long get(int index, int l, int r, int x) { if(l > r || r < x || x < l) return -inf; if(l == r) return st[index].mx; propagate(index); int mid = (l + r) / 2; return max(get(2 * index, l, mid, x), get(2 * index + 1, mid + 1, r, x)); } int walk(int index, int l, int r, int x, long long val) { if(l > r || r < x) return -1; if(l == r) return l - 1; if(st[index].mx < val) return -1; propagate(index); int mid = (l + r) / 2; long long L = walk(2 * index, l, mid, x, val); if(L != -1) return L; return walk(2 * index + 1, mid + 1, r, x, val); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++) cin >> a[i] >> s[i] >> p[i]; for(int i = 1; i <= m; i++) cin >> b[i] >> t[i] >> q[i]; for(int i = 2; i <= n; i++) a[i] += a[i - 1]; for(int i = 2; i <= m; i++) b[i] += b[i - 1]; for(int i = 1; i <= n; i++) { int l = 0, r = m; int ans = l; while(l <= r) { int mid = (l + r) / 2; if(a[i] + b[mid] <= s[i]) { ans = mid; l = mid + 1; } else r = mid - 1; } x[i] = ans; } for(int i = 1; i <= m; i++) { int l = 0, r = n; int ans = l; while(l <= r) { int mid = (l + r) / 2; if(a[mid] + b[i] <= t[i]) { ans = mid; l = mid + 1; } else r = mid - 1; } y[i] = ans; } long long add = 0; for(int i = 1; i <= n; i++) { add += p[i]; if(x[i] < m) all[x[i] + 1].push_back({i - 1, -p[i]}); } for(int i = 1; i <= m; i++) all[i].push_back({y[i], q[i]}); for(int i = 1; i <= m; i++) { sort(all[i].begin(), all[i].end(), [&](pt p1, pt p2) { return p1.y < p2.y; }); } for(int i = 0; i <= m; i++) { for(pt p : all[i]) { int y = p.y; long long val = p.val; update(1, 0, n, 1, y, val); long long mx = get(1, 0, n, y); int nxt = walk(1, 0, n, y + 1, mx); modify(1, 0, n, y, nxt, mx); } } // for(int i = 1; i <= m; i++) { // for(pt p : all[i]) cout << i << " " << p.y << " " << p.val << "\n"; // } // for(int i = 1; i <= n; i++) cout << x[i] << " "; // cout << "\n"; // for(int i = 1; i <= m; i++) cout << y[i] << " "; // cout << "\n"; cout << get(1, 0, n, n) + add; return 0; }
#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...