Submission #1080341

#TimeUsernameProblemLanguageResultExecution timeMemory
1080341vjudge1Food Court (JOI21_foodcourt)C++17
100 / 100
492 ms83952 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt") #include <bits/stdc++.h> #define taskname "" #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define int long long #define ll long long #define ld long double #define pb push_back #define ff first #define ss second #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> #define vii vector<pii> using namespace std; const int mxN = 250000 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; struct node { ll sum_plus, sum_minus, idx; pll pref_min; node() { sum_plus = sum_minus = idx = 0; pref_min = {0, mod}; } node operator + (const node &o) { node res; res.sum_plus = sum_plus + o.sum_plus; res.sum_minus = sum_minus + o.sum_minus; res.pref_min = min(pref_min, {sum_plus - sum_minus + o.pref_min.ff, o.pref_min.ss}); return res; } } segtree[4 * mxN]; int n, m, q, ans[mxN]; vector<vector<ll>> query; vi query_time[mxN], all_query; vii actual_query[mxN]; void update(int l, int r, int idx, int pos, int val) { if(l == r) { if(val > 0) { if(query[pos][0] == 1) segtree[idx].sum_plus = query[pos][2]; else if(query[pos][0] == 2) segtree[idx].sum_minus = query[pos][1]; segtree[idx].pref_min = {min(segtree[idx].sum_plus, -segtree[idx].sum_minus), pos}; segtree[idx].idx = pos; } else { segtree[idx] = node(); } return; } int mid = (l + r) >> 1; if(pos <= mid) update(l, mid, idx << 1, pos, val); else update(mid + 1, r, idx << 1 | 1, pos, val); segtree[idx] = segtree[idx << 1] + segtree[idx << 1 | 1]; } node get(int l, int r, int idx, int u, int v) { if(v < u) return node(); if(u <= l && r <= v) { return segtree[idx]; } int mid = (l + r) >> 1; if(v <= mid) return get(l, mid, idx << 1, u, v); else if(mid + 1 <= u) return get(mid + 1, r, idx << 1 | 1, u, v); else return get(l, mid, idx << 1, u, v) + get(mid + 1, r, idx << 1 | 1, u, v); } int huutuannguvailon(int cur_l, int cur_r, ll k) { int l = 1, r = q, idx = 1; while(l < r) { int mid = (l + r) >> 1; if(k > segtree[idx << 1].sum_plus) { k -= segtree[idx << 1].sum_plus; idx = idx << 1 | 1, l = mid + 1; } else { idx <<= 1, r = mid; } } return query[l][1]; } void solve() { cin >> n >> m >> q; query.pb({}); for(int i = 1; i <= q; ++i) { int type; cin >> type; vector<ll> tmp = {type}; if(type == 1) { int l, r; cin >> l >> r; query_time[l].emplace_back(i); query_time[r + 1].emplace_back(-i); ll k, c; cin >> c >> k; tmp.emplace_back(c); tmp.emplace_back(k); } else if(type == 2) { int l, r; cin >> l >> r; query_time[l].emplace_back(i); query_time[r + 1].emplace_back(-i); ll k; cin >> k; tmp.emplace_back(k); } else { all_query.emplace_back(i); ll cur, k; cin >> cur >> k; actual_query[cur].emplace_back(i, k); } query.pb(tmp); } for(int i = 1; i <= n; ++i) { for(int &val : query_time[i]) { if(val > 0) update(1, q, 1, val, 1); else update(1, q, 1, -val, -1); } int cope = segtree[1].pref_min.ss; if(cope == mod) { for(auto &[idx, k] : actual_query[i]) ans[idx] = 0; continue; } for(auto &[idx, k] : actual_query[i]) { auto cur = get(1, q, 1, 1, idx); cope = cur.pref_min.ss; if(cope == mod || cope == idx) { ans[idx] = 0; continue; } auto cur1 = get(1, q, 1, cope, idx); if(query[cope][0] == 2) cur1.sum_minus -= query[cope][1]; ll actual_k = k + cur1.sum_minus; if(actual_k > cur1.sum_plus) { ans[idx] = 0; continue; } ans[idx] = huutuannguvailon(cope, idx, actual_k + cur.sum_plus - cur1.sum_plus); } } for(int &idx : all_query) cout << ans[idx] << endl; } signed main() { #ifndef CDuongg if(fopen(taskname".inp", "r")) assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout)); #else freopen("bai3.inp", "r", stdin); freopen("bai3.out", "w", stdout); auto start = chrono::high_resolution_clock::now(); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); #ifdef CDuongg auto end = chrono::high_resolution_clock::now(); // cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '='; // cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl; #endif }
#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...