Submission #708400

#TimeUsernameProblemLanguageResultExecution timeMemory
708400uroskFood Court (JOI21_foodcourt)C++14
100 / 100
708 ms69768 KiB
#define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include "bits/stdc++.h" //#include <ext/pb_ds/tree_policy.hpp> //#include <ext/pb_ds/assoc_container.hpp> #define ld double #define ll long long #define llinf 100000000000000000LL // 10^17 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); using namespace std; #define maxn 250005 ll n,m,q; vector<pll> tq[maxn],t2q[maxn],Q[maxn]; ll tip[maxn]; pll t[2*maxn]; ll t2[2*maxn]; ll ls[2*maxn],rs[2*maxn],tsz = 0,root = 0; ll ans[maxn]; ll c[maxn]; pll mrg(pll a,pll b){ return {a.fi+b.fi,max(b.sc,b.fi+a.sc)}; } void init(ll &v,ll tl,ll tr){ if(!v) v = ++tsz; if(tl==tr){return;} ll mid = (tl+tr)/2; init(ls[v],tl,mid); init(rs[v],mid+1,tr); } void upd(ll v,ll tl,ll tr,ll i,ll x){ if(tl==tr){t[v] = {x,max(0LL,x)};return;} ll mid = (tl+tr)/2; if(i<=mid) upd(ls[v],tl,mid,i,x); else upd(rs[v],mid+1,tr,i,x); t[v] = mrg(t[ls[v]],t[rs[v]]); } pll get(ll v,ll tl,ll tr,ll l,ll r){ if(l>r||tl>tr||tl>r||tr<l) return {0LL,0LL}; if(tl>=l&&tr<=r) return t[v]; ll mid = (tl+tr)/2; return mrg(get(ls[v],tl,mid,l,r),get(rs[v],mid+1,tr,l,r)); } void upd2(ll v,ll tl,ll tr,ll i,ll x){ if(tl==tr){t2[v] = x;return;} ll mid = (tl+tr)/2; if(i<=mid) upd2(ls[v],tl,mid,i,x); else upd2(rs[v],mid+1,tr,i,x); t2[v] = t2[ls[v]] + t2[rs[v]]; } ll sum(ll v,ll tl,ll tr,ll l,ll r){ if(l>r||tl>tr||tl>r||tr<l) return 0; if(tl>=l&&tr<=r) return t2[v]; ll mid = (tl+tr)/2; return sum(ls[v],tl,mid,l,r) + sum(rs[v],mid+1,tr,l,r); } ll walk(ll v,ll tl,ll tr,ll x){ if(tl==tr){ if(t2[v]<x) return tl; return tl-1; } ll mid = (tl+tr)/2; if(t2[ls[v]]>x) return walk(ls[v],tl,mid,x); return walk(rs[v],mid+1,tr,x-t2[ls[v]]); } void tc(){ cin >> n >> m >> q; init(root,1,q); for(ll i = 1;i<=q;i++){ cin >> tip[i]; if(tip[i]==1){ ll l,r,x; cin >> l >> r >> c[i] >> x; tq[l].pb({i,x}); tq[r+1].pb({i,0}); t2q[l].pb({i,x}); t2q[r+1].pb({i,0}); }else if(tip[i]==2){ ll l,r,x; cin >> l >> r >> x; tq[l].pb({i,-x}); tq[r+1].pb({i,0}); }else{ ll x,y; cin >> x >> y; Q[x].pb({i,y}); } } for(ll i = 1;i<=n;i++){ for(pll p : tq[i]) upd(1,1,q,p.fi,p.sc); for(pll p : t2q[i]) upd2(1,1,q,p.fi,p.sc); for(pll p : Q[i]){ ll id = p.fi; ll x = get(1,1,q,1,id).sc,y = p.sc; if(x<y) ans[id] = 0; else{ ll d = sum(1,1,q,1,id) - x + y; ll j = walk(1,1,q,d-1) + 1; ans[id] = c[j]; } } } for(ll i = 1;i<=q;i++){ if(tip[i]==3) cout<<ans[i]<<endl; } } int main(){ daj_mi_malo_vremena int t; t = 1; while(t--){ tc(); } return 0; } /** 3 5 7 1 2 3 5 2 1 1 2 2 4 3 2 3 2 1 3 3 3 1 2 1 2 3 4 2 3 3 2 3 4 7 1 1 2 1 1 1 1 3 4 1 2 2 3 1 2 1 3 1 1 1 2 2 1 3 1 1 3 3 2 183326 218318 22 1 106761 160918 151683 574906362 3 68709 1 1 29240 156379 22166 957318472 1 14054 181502 82845 97183925 2 112033 122908 587808357 2 57819 160939 215041262 3 36674 524274467 1 35854 69866 32334 322730299 1 1384 7230 115069 454256926 1 44192 158235 8750 84192710 3 54457 1077490708 2 10592 110384 979714505 2 44594 79244 311724477 3 160965 97183926 1 88748 101697 39148 373927458 3 41166 58039001 1 91501 137591 205480 958877326 2 77775 169655 135756956 1 12497 57047 60918 15666764 1 47839 51716 144688 732270998 3 114514 774994894 3 48645 169986425 **/
#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...