제출 #170752

#제출 시각아이디문제언어결과실행 시간메모리
170752gs18103Two Dishes (JOI19_dishes)C++14
0 / 100
414 ms39728 KiB
#include <bits/stdc++.h> #define fi first #define se second #define eb emplace_back #define em emplace #define all(v) v.begin(), v.end() #define my_assert cout << "!" << endl; using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const int MAX = 1010101; const int INF = (1 << 30) - 1; const ll LINF = 1LL << 60; int n, m; ll A[MAX], S[MAX], P[MAX]; ll B[MAX], T[MAX], Q[MAX]; ll sumA[MAX], sumB[MAX], ans; ll tree[4*MAX], lazy[4*MAX]; void update_lazy(int node, int s, int e) { tree[node] += lazy[node]; if(s != e) { lazy[node*2] += lazy[node]; lazy[node*2+1] += lazy[node]; } lazy[node] = 0; } void update(int node, int s, int e, int r, ll val, ll mx) { update_lazy(node, s, e); if(s > r && tree[node] >= mx) return; if(e <= r) { lazy[node] += val; update_lazy(node, s, e); return; } else if(s > r) { lazy[node] = mx - tree[node]; update_lazy(node, s, e); return; } int mi = (s + e) / 2; update(node*2, s, mi, r, val, mx); mx = max(mx, tree[node*2]); update(node*2+1, mi+1, e, r, val, mx); tree[node] = tree[node*2+1]; } ll cal(int node, int s, int e) { update_lazy(node, s, e); if(s == e) return tree[node]; int mi = (s + e) / 2; return cal(node*2+1, mi+1, e); } struct point { int x, y; ll val; point(int x, int y, ll val) : x(x), y(y), val(val) {} }; vector <point> po; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> A[i] >> S[i] >> P[i]; sumA[i] = sumA[i-1] + A[i]; } for(int i = 1; i <= m; i++) { cin >> B[i] >> T[i] >> Q[i]; sumB[i] = sumB[i-1] + B[i]; ans += Q[i]; } for(int i = 1; i <= n; i++) { int temp = upper_bound(sumB, sumB+m+1, S[i] - sumA[i]) - sumB - 1; if(temp >= 0) po.eb(i, temp, P[i]); } for(int i = 1; i <= m; i++) { int temp = upper_bound(sumA, sumA+n+1, T[i] - sumB[i]) - sumA - 1; if(temp < 0) ans -= Q[i]; else if(temp < n) po.eb(temp+1, i-1, -Q[i]); } sort(all(po), [](point a, point b) { if(a.x == b.x) return a.y > b.y; return a.x < b.x; }); for(auto i : po) { update(1, 0, m, i.y, i.val, 0); } cout << cal(1, 0, m) + ans; }
#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...