Submission #1172151

#TimeUsernameProblemLanguageResultExecution timeMemory
1172151jakubmz2Two Dishes (JOI19_dishes)C++20
0 / 100
264 ms60880 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MAXN = 1e6 + 5; ll c1[MAXN]; ll c2[MAXN]; ll t1[MAXN]; ll t2[MAXN]; ll p1[MAXN]; ll p2[MAXN]; ll pref1[MAXN]; ll pref2[MAXN]; ll INF = 1e18; struct d{ ll maks = 0; ll wdol = 0; }; ll base = 1 << 20; d drzew[1 << 21]; ll off = 0; struct comp{ bool operator()(const pair<ll,ll> &p1, const pair<ll,ll> &p2) const { if(p1.first != p2.first) return p1.first < p2.first; if(p1.second != p2.second) return p1.second > p2.second; return false; } }; map<pair<ll,ll>, ll, comp> points; void wdol(ll w){ ll d = drzew[w].wdol; drzew[2 * w].wdol += d; drzew[2 * w].maks += d; drzew[2 * w + 1].maks += d; drzew[2 * w + 1].wdol += d; drzew[w].wdol = 0; return; } ll oblmax(ll w, ll a, ll b, ll akt_a, ll akt_b){ //cout << a << " " << akt_a << " " << akt_b << " " << b << " przedz\n"; if(a <= akt_a and akt_b <= b) { return drzew[w].maks; } if(akt_a > b or akt_b < a) return -INF; wdol(w); ll mid = (akt_a + akt_b) / 2; return max(oblmax(2 * w, a, b, akt_a, mid), oblmax(2 * w + 1, a, b, mid + 1, akt_b)); } void ustaw(ll w, ll akt_a, ll akt_b, ll ind, ll val){ if(akt_a == akt_b){ drzew[w] = {max(drzew[w].maks, val), 0}; return; } wdol(w); ll mid = (akt_a + akt_b) / 2; if(ind <= mid){ ustaw(2 * w, akt_a, mid, ind, val); } else{ ustaw(2 * w + 1, mid + 1, akt_b, ind, val); } return; } void akt(ll w, ll a, ll b, ll akt_a, ll akt_b, ll val){ if(a <= akt_a and akt_b <= b){ drzew[w].maks += val; drzew[w].wdol += val; return; } if(akt_a > b or akt_b < a) return; wdol(w); ll mid = (akt_a + akt_b) / 2; akt(2 * w, a, b, akt_a, mid, val); akt(2 * w + 1, a, b, mid + 1, akt_b, val); drzew[w].maks = max(drzew[2 * w].maks, drzew[2 * w + 1].maks); return; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, m; cin >> n >> m; for(ll i = 1; i < 2 * base; ++i){ drzew[i] = {0, 0}; } for(ll i = 1; i <= n; ++i){ cin >> c1[i] >> t1[i] >> p1[i]; pref1[i] = pref1[i - 1] + c1[i]; } for(ll i = 1; i <= m; ++i){ cin >> c2[i] >> t2[i] >> p2[i]; pref2[i] = pref2[i - 1] + c2[i]; } for(ll i = 1; i <= n; ++i){ if(pref1[i] > t1[i]) continue; if(pref1[i] + pref2[m] <= t1[i]){ //cout << i << " wyj\n"; off += p1[i]; continue; } ll p = 1; ll k = m; while(p != k){ ll sr = (p + k + 1) / 2; //cout << p << " " << k << " bs1\n"; if(pref1[i] + pref2[sr] <= t1[i]){ p = sr; } else{ k = sr - 1; } } points[{i - 1, p + 1}] += p1[i]; } for(ll i = 1; i <= m; ++i){ if(pref2[i] > t2[i]) continue; if(pref2[i] + pref1[n] <= t2[i]){ off += p2[i]; continue; } ll p = 1; ll k = n; while(p != k){ //cout << p << " " << k << " bs2\n"; ll sr = (p + k + 1) / 2; if(pref2[i] + pref1[sr] <= t2[i]){ p = sr; } else{ k = sr - 1; } } off += p2[i]; points[{p, i}] -= p2[i]; } for(auto u : points){ ll y = u.first.second; ll val = u.second; ll mx = oblmax(1, 0, y - 1, 0, base - 1); ustaw(1, 0, base - 1, y, mx); akt(1, 0, y, 0, base, val); } cout << drzew[1].maks + off << "\n"; 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...