제출 #386988

#제출 시각아이디문제언어결과실행 시간메모리
386988keko37푸드 코트 (JOI21_foodcourt)C++14
0 / 100
350 ms42476 KiB
#include<bits/stdc++.h> using namespace std; typedef long long llint; typedef pair <llint, llint> pi; const int MAXN = 250005; int n, m, q, ofs = 1; llint tip[MAXN], lef[MAXN], rig[MAXN], k[MAXN], col[MAXN], sol[MAXN]; pi t[MAXN * 4]; llint sum[MAXN]; vector <pi> v[MAXN]; vector <int> u[MAXN]; pi spoji (pi a, pi b) { return {a.first + b.first, max(a.second + b.first, b.second)}; } void update (int pos, llint val) { pos += ofs; t[pos].first += val; t[pos].second = max(t[pos].first, 0LL); sum[pos] = t[pos].second; pos /= 2; while (pos > 0) { t[pos] = spoji(t[pos * 2], t[pos * 2 + 1]); sum[pos] = sum[2 * pos] + sum[2 * pos + 1]; pos /= 2; } } pi upit (int x, int from, int to, int lo, int hi) { if (from <= lo && hi <= to) return t[x]; if (to < lo || hi < from) return {0, 0}; return spoji(upit(2 * x, from, to, lo, (lo + hi) / 2), upit(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi)); } int nadi (int x, llint val) { if (x >= ofs) return x; if (val <= sum[2 * x + 1]) return nadi(2 * x + 1, val); return nadi(2 * x, val - sum[2 * x + 1]); } int bs (int pos, llint val) { int curr = pos + ofs; llint curr_sum = sum[curr]; if (val <= curr_sum) return pos; while (curr > 1) { if (curr % 2 == 0) { curr /= 2; } else { if (val > curr_sum + sum[curr - 1]) { curr_sum += sum[curr - 1]; curr /= 2; } else { return nadi(curr - 1, val - curr_sum) - ofs; } } } return 0; } void get_curr_siz () { for (int i = 1; i <= q; i++) { if (tip[i] == 1) { v[lef[i]].push_back({k[i], i}); v[rig[i] + 1].push_back({-k[i], i}); } else if (tip[i] == 2) { v[lef[i]].push_back({-k[i], i}); v[rig[i] + 1].push_back({k[i], i}); } else { u[lef[i]].push_back(i); } } while (ofs < q + 1) ofs *= 2; for (int pos = 1; pos <= n; pos++) { for (auto pp : v[pos]) { llint val = pp.first; int ind = pp.second; update(ind, val); } for (auto i : u[pos]) { llint siz = upit(1, 0, i, 0, ofs - 1).second; if (k[i] <= siz) { //sol[i] = col[bs(i, siz - k[i] + 1)]; sol[i] = 1; } } } } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> q; for (int i = 1; i <= q; i++) { cin >> tip[i]; if (tip[i] == 1) { cin >> lef[i] >> rig[i] >> col[i] >> k[i]; } else if (tip[i] == 2) { cin >> lef[i] >> rig[i] >> k[i]; } else { cin >> lef[i] >> k[i]; } } get_curr_siz(); for (int i = 1; i <= q; i++) { if (tip[i] != 3) continue; cout << sol[i] << '\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...