제출 #1081242

#제출 시각아이디문제언어결과실행 시간메모리
1081242Trent푸드 코트 (JOI21_foodcourt)C++17
68 / 100
1064 ms47620 KiB
#include <iostream> #include "bits/stdc++.h" #define forR(i, x) for(int i=0; i < (x); ++i) #define REP(i, a, b) for(int i=(a); i<(b); ++i) #define all(x) x.begin(), x.end() #define boost() cin.sync_with_stdio(0); cin.tie(0) #define asst(x) if(!(x)) exit(1) using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; const int MN = 3e5 + 10; int len[MN]; struct ev{ int ti; ll to; }; ll ch[MN]; int c[MN]; bool us[MN]; vector<ev> evs[MN]; struct query{ int ai, i; ll b; }; vector<query> qus[MN]; int ans[MN]; struct node { ll ps, psm; ll nSum; }; node seg[4 * MN]; node comb(node a, node b) { return {a.ps + b.ps, min(a.psm, a.ps + b.psm), a.nSum + b.nSum}; } void upd(int v, int nl, int nr, int i, ll to) { if(nl == i && nr == i) seg[v] = {to, min(0LL, to), to < 0 ? to : 0}; else { int mid = (nl+nr)/2; if(i <= mid) upd(2*v, nl, mid, i, to); else upd(2*v+1, mid+1, nr, i, to); seg[v] = comb(seg[2*v], seg[2*v+1]); } } node qu(int v, int nl, int nr, int l, int r) { if(l > r) return {0, 0, 0}; if(nl == l && nr == r) return seg[v]; int mid = (nl+nr)/2; return comb(qu(2*v, nl, mid, l, min(mid, r)), qu(2*v+1, mid+1, nr, max(mid+1, l), r)); } int main(){ boost(); int n, m, q; cin >> n >> m >> q; int ai=0; forR(i, q){ int ty; cin >> ty; if(ty == 1){ int l, r, k; cin >> l >> r >> c[i] >> k; evs[l].push_back({i, k}); evs[r+1].push_back({i, 0}); } else if(ty == 2){ int l, r, k; cin >> l >> r >> k; evs[l].push_back({i, -k}); evs[r+1].push_back({i, 0}); } else { int a; ll b; cin >> a >> b; qus[a].push_back({ai++, i, b}); } } REP(i, 1, n+1){ for(auto [ti, to] : evs[i]) { ch[ti] = to; upd(1, 0, q-1, ti, to); } for(auto [ai, ti, b] : qus[i]) { int lo=-1, hi=ti+1; while(hi-lo > 1) { int mid = (lo+hi)/2; node upTo = qu(1, 0, q-1, 0, mid); node after = qu(1, 0, q-1, mid+1, ti); if(upTo.ps - upTo.psm + after.nSum >= b) hi = mid; else lo = mid; } if(hi <= ti) { ans[ai] = c[hi]; } else ans[ai] = 0; } } forR(i, ai) cout << ans[i] << '\n'; }
#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...