Submission #392601

#TimeUsernameProblemLanguageResultExecution timeMemory
392601nvmdavaFood Court (JOI21_foodcourt)C++17
100 / 100
562 ms80028 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 1000005; const ll MOD = 1000000007; const ll INF = 0x3f3f3f3f3f3f3f3f; vector<pair<int, ll> > upd[N], que[N]; int ans[N]; int col[N]; ll sum[N], p1[N], p2[N]; void update(int id, int l, int r, int x, int v){ if(l > x || r < x) return; if(l == r){ if(v > 0){ if(p1[id] < 0) p1[id] = 0; else p2[id] = sum[id] = v; } else { if(p2[id] > 0) p2[id] = sum[id] = 0; else p1[id] = v; } return; } int m = (l + r) >> 1; update(id << 1, l, m, x, v); update(id << 1 | 1, m + 1, r, x, v); sum[id] = sum[id << 1] + sum[id << 1 | 1]; p2[id] = max(p2[id << 1] + p1[id << 1 | 1], 0LL) + p2[id << 1 | 1]; p1[id] = p1[id << 1] + min(p2[id << 1] + p1[id << 1 | 1], 0LL); } int query(int id, int l, int r, ll k){ if(l == r) return l; int m = (l + r) >> 1; if(sum[id << 1] >= k) return query(id << 1, l, m, k); return query(id << 1 | 1, m + 1, r, k - sum[id << 1]); } void query2(int id, int l, int r, int x, ll& s1, ll& c1){ if(l > x) return; if(r <= x){ s1 += sum[id]; c1 = max(c1 + p1[id], 0LL) + p2[id]; return; } int m = (l + r) >> 1; query2(id << 1, l, m, x, s1, c1); query2(id << 1 | 1, m + 1, r, x, s1, c1); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, q; cin>>n>>m>>q; for(int t, i = 1; i <= q; ++i){ cin>>t; ans[i] = -1; if(t == 1){ int l, r, c; ll k; cin>>l>>r>>c>>k; col[i] = c; upd[l].push_back({i, k}); upd[r + 1].push_back({i, -k}); } else if(t == 2){ int l, r; ll k; cin>>l>>r>>k; upd[l].push_back({i, -k}); upd[r + 1].push_back({i, k}); } else { int a; ll b; cin>>a>>b; que[a].push_back({i, b}); } } for(int i = 1; i <= n; ++i){ for(auto &[x, v] : upd[i]) update(1, 1, q, x, v); for(auto &[x, v] : que[i]){ ll s1 = 0, c1 = 0; query2(1, 1, q, x, s1, c1); if(c1 < v){ ans[x] = 0; continue; } ans[x] = col[query(1, 1, q, v + s1 - c1)]; } } for(int i = 1; i <= q; ++i) if(ans[i] != -1)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...