Submission #953025

#TimeUsernameProblemLanguageResultExecution timeMemory
953025WonderfulWhaleFood Court (JOI21_foodcourt)C++17
13 / 100
690 ms113528 KiB
#include<bits/stdc++.h> using namespace std; #define INT __int128 #define int int64_t #define pb push_back #define pii pair<int, int> #define st first #define nd second #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define ll __int128 const int INF = 1e17; const int MAXN = 250'009; namespace special { const int MAXN = 500001; // 1-based int N = 400000; ll A[MAXN]; struct Node { ll sum; // Sum tag ll min1; // Min value ll min2; // Second Min value ll minc; // Min value count ll lazy; // Lazy tag } T[MAXN * 4]; void merge(int t) { // sum T[t].sum = T[t << 1].sum + T[t << 1 | 1].sum; if (T[t << 1].min1 == T[t << 1 | 1].min1) { T[t].min1 = T[t << 1].min1; T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min2); T[t].minc = T[t << 1].minc + T[t << 1 | 1].minc; } else { if (T[t << 1].min1 < T[t << 1 | 1].min1) { T[t].min1 = T[t << 1].min1; T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min1); T[t].minc = T[t << 1].minc; } else { T[t].min1 = T[t << 1 | 1].min1; T[t].min2 = min(T[t << 1].min1, T[t << 1 | 1].min2); T[t].minc = T[t << 1 | 1].minc; } } } void push_add(int t, int tl, int tr, ll v) { if (v == 0) { return; } T[t].sum += (tr - tl + 1) * v; T[t].min1 += v; if (T[t].min2 != INF) { T[t].min2 += v; } T[t].lazy += v; } // corresponds to a chmax update void push_min(int t, ll v, bool l) { if (v <= T[t].min1) { return; } T[t].sum -= T[t].min1 * T[t].minc; T[t].min1 = v; T[t].sum += T[t].min1 * T[t].minc; } void pushdown(int t, int tl, int tr) { if (tl == tr) return; // sum int tm = (tl + tr) >> 1; push_add(t << 1, tl, tm, T[t].lazy); push_add(t << 1 | 1, tm + 1, tr, T[t].lazy); T[t].lazy = 0; // min push_min(t << 1, T[t].min1, tl == tm); push_min(t << 1 | 1, T[t].min1, tm + 1 == tr); } void build(int t = 1, int tl = 0, int tr = N - 1) { T[t].lazy = 0; if (tl == tr) { T[t].sum = T[t].min1 = A[tl]; T[t].min2 = INF; return; } int tm = (tl + tr) >> 1; build(t << 1, tl, tm); build(t << 1 | 1, tm + 1, tr); merge(t); } void update_add(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) { // cerr << "change!!!\n"; if (r < tl || tr < l) { return; } if (l <= tl && tr <= r) { push_add(t, tl, tr, v); return; } pushdown(t, tl, tr); int tm = (tl + tr) >> 1; update_add(l, r, v, t << 1, tl, tm); update_add(l, r, v, t << 1 | 1, tm + 1, tr); merge(t); } void update_chmax(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) { if (r < tl || tr < l || v <= T[t].min1) { return; } if (l <= tl && tr <= r && v < T[t].min2) { push_min(t, v, tl == tr); return; } pushdown(t, tl, tr); int tm = (tl + tr) >> 1; update_chmax(l, r, v, t << 1, tl, tm); update_chmax(l, r, v, t << 1 | 1, tm + 1, tr); merge(t); } ll query_sum(int l, int r, int t = 1, int tl = 0, int tr = N - 1) { if (r < tl || tr < l) { return 0; } if (l <= tl && tr <= r) { return T[t].sum; } pushdown(t, tl, tr); int tm = (tl + tr) >> 1; return query_sum(l, r, t << 1, tl, tm) + query_sum(l, r, t << 1 | 1, tm + 1, tr); } } struct SegTree { const static int T = 1<<20; int t[2*T]; void update(int l, int r, int val) { l+=T, r+=T; t[l]+=val; if(l!=r) { t[r]+=val; } while(l/2!=r/2) { if(l%2==0) { t[l+1]+=val; } if(r%2==1) { t[r-1]+=val; } l/=2; r/=2; } } int query(int x) { x+=T; int ret = 0; while(x){ ret += t[x]; x/=2; } return ret; } } seg; struct SegTree2 { const static int T = 1<<18; pii t[2*T]; int lz[2*T]; SegTree2() { for(int i=T;i<2*T;i++) { t[i] = {INF, i-T}; } for(int i=T-1;i;i--) { t[i] = min(t[2*i], t[2*i+1]); } } void push(int v) { int l = 2*v, r = 2*v+1; t[l].st += lz[v]; t[r].st += lz[v]; lz[l] += lz[v]; lz[r] += lz[v]; lz[v] = 0; } void update(int l, int r, int val, int tl=0, int tr=T-1, int v=1) { if(l>r) return; if(l==tl&&r==tr) { t[v].st += val; lz[v] += val; return; } push(v); int tm = (tl+tr)/2; update(l, min(r, tm), val, tl, tm, 2*v); update(max(tm+1, l), r, val, tm+1, tr, 2*v+1); t[v] = min(t[2*v], t[2*v+1]); } pii query(int l, int r, int tl=0, int tr=T-1, int v=1) { if(l>r) return make_pair(INF, -1); if(l==tl&&r==tr) { return t[v]; } push(v); int tm = (tl+tr)/2; return min(query(l, min(r, tm), tl, tm, 2*v), query(max(tm+1, l), r, tm+1, tr, 2*v+1)); } } seg2; vector<tuple<int, int, int, int>> Q; int tab[MAXN]; int lim[MAXN]; pii info[MAXN]; int ans[MAXN]; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); vector<pii> zap; int n, m, q; cin >> n >> m >> q; int cnt = 0; int cnt3 = 0; special::build(); for(int i=0;i<q;i++) { int type; cin >> type; if(type==1) { int l, r, c, k; cin >> l >> r >> k >> c; tab[cnt] = k; Q.pb({l, r, c, k}); cnt++; seg.update(l, r, c); special::update_add(l, r, c); } if(type==2) { int l, r, c; cin >> l >> r >> c; special::update_add(l, r, -c); special::update_chmax(l, r, 0); } if(type==3) { int a, b; cin >> a >> b; int diff = seg.query(a)-special::query_sum(a, a); b += diff; info[cnt3] = {cnt, b}; zap.pb({a, cnt3++}); } } sort(all(zap)); for(int i=0;i<cnt3;i++) { int num = zap[i].nd; seg2.update(i, i, -INF+info[num].nd); pii X = seg2.query(i, i); } for(int i=0;i<cnt;i++) { auto [l, r, C, k] = Q[i]; int s = -1; int e = cnt3; while(e-s>1) { int m = (e+s)/2; if(zap[m].st>=l) e = m; else s = m; } int S = e; s = -1, e = cnt3; while(e-s>1) { int m = (e+s)/2; if(zap[m].st<=r) s = m; else e = m; } int E = s; seg2.update(S, E, -C); while(true) { pii x = seg2.query(0, cnt3-1); if(x.st>0) break; if(i<info[zap[x.nd].nd].st) ans[zap[x.nd].nd] = tab[i]; seg2.update(x.nd, x.nd, INF); } } for(int i=0;i<cnt3;i++) { cout << ans[i] << "\n"; } }

Compilation message (stderr)

foodcourt.cpp: In function 'int32_t main()':
foodcourt.cpp:262:7: warning: variable 'X' set but not used [-Wunused-but-set-variable]
  262 |   pii X = seg2.query(i, i);
      |       ^
#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...