제출 #1081221

#제출 시각아이디문제언어결과실행 시간메모리
1081221Trent푸드 코트 (JOI21_foodcourt)C++17
7 / 100
1067 ms34640 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 nSum; }; node seg[4 * MN]; void upd(int v, int nl, int nr, int i, ll to) { if(nl == i && nr == i) seg[v] = {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].nSum = seg[2*v].nSum + seg[2*v+1].nSum; } } ll nSum(int v, int nl, int nr, int l, int r) { if(l > r) return 0; if(nl == l && nr == r) return seg[v].nSum; int mid = (nl+nr)/2; return nSum(2*v, nl, mid, l, min(mid, r)) + nSum(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 j = 0; bool found = false; ll cur = 0; for(; j <= ti && !found;) { cur = max(0LL, cur + ch[j]); if(cur + nSum(1, 0, q-1, j+1, ti) >= b) { found = true; } else { ++j; } } if(found) { ans[ai] = c[j]; } 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...