Submission #789992

#TimeUsernameProblemLanguageResultExecution timeMemory
789992someoneTwo Dishes (JOI19_dishes)C++14
100 / 100
2897 ms174124 KiB
#include <bits/stdc++.h> #define int long long using namespace std; struct Point { int x, y, val; }; const int M = 1 << 20, N = 2 * M, INF = 1e18 + 42; int maxi[N], tag[N]; inline void applyOp(int i, int add) { tag[i] += add; maxi[i] += add; } inline void propage(int i) { applyOp(i*2, tag[i]); applyOp(i*2+1, tag[i]); tag[i] = 0; } void setVal(int i, int deb, int fin, int pos, int val) { if(pos < deb || fin <= pos) return; if(fin - deb == 1) { maxi[i] = val; return; } propage(i); int mid = ((deb + fin) >> 1); setVal(i*2, deb, mid, pos, val); setVal(i*2+1, mid, fin, pos, val); maxi[i] = max(maxi[i*2], maxi[i*2+1]); } int update(int i, int deb, int fin, int l, int r, int add) { if(r <= deb || fin <= l) return -2*INF; if(l <= deb && fin <= r) { applyOp(i, add); return maxi[i]; } propage(i); int mid = ((deb + fin) >> 1), ans = max(update(i*2, deb, mid, l, r, add), update(i*2+1, mid, fin, l, r, add)); maxi[i] = max(maxi[i*2], maxi[i*2+1]); return ans; } vector<Point> point; int score = 0, ans = 0, sz[2], a[2][M], t[2][M], pt[2][M], pos[2][M]; void solve() { for(int i = 0; i < N; i++) tag[i] = 0, maxi[i] = -INF; for(int i = 0; i < 2; i++) for(int j = 1; j <= sz[i]; j++) a[i][j] += a[i][j-1]; a[0][sz[0]+1] = a[1][sz[1]+1] = INF; for(int i = 0; i < 2; i++) for(int j = 1; j <= sz[i]; j++) pos[i][j] = (int)(upper_bound(a[1-i], a[1-i] + sz[1-i] + 1, t[i][j] - a[i][j]) - a[1-i]) - 1; for(int j = 0; j <= sz[0]; j++) if(pos[0][j] != -1) point.push_back({j, pos[0][j], pt[0][j]}); for(int j = 1; j <= sz[1]; j++) { if(pos[1][j] != -1) { score += pt[1][j]; if(pos[1][j] != sz[0]) point.push_back({pos[1][j]+1, j-1, -pt[1][j]}); } } point.push_back({sz[0], sz[1], 0}); sort(point.begin(), point.end(), [](Point p1, Point p2) { if(p1.x == p2.x) return p1.y < p2.y; return p1.x > p2.x; }); for(int i = 1; i < (int)point.size(); i++) if(point[i].x == point[i-1].x && point[i].y == point[i-1].y) { point[i-1].x = point[i-1].y = -1; point[i].val += point[i-1].val; point[i-1].val = 0; } for(int i = 0; i < (int)point.size(); i++) { if(point[i].x != -1) { int val = update(1, 0, M, point[i].y, M, 0); if(point[i].x == sz[0]) val = 0; setVal(1, 0, M, point[i].y, val); update(1, 0, M, 0, point[i].y+1, point[i].val); if(point[i].x == 0 && point[i].y == 0) ans = val; } } cout << ans + score << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> sz[0] >> sz[1]; for(int i = 0; i < 2; i++) for(int j = 1; j <= sz[i]; j++) cin >> a[i][j] >> t[i][j] >> pt[i][j]; solve(); }
#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...