Submission #1240934

#TimeUsernameProblemLanguageResultExecution timeMemory
1240934hamanp87Food Court (JOI21_foodcourt)C++17
24 / 100
75 ms55044 KiB
#include<bits/stdc++.h> using namespace std; using ll=long long; //#pragma GCC optimize("03,unroll-loops") //#pragma GCC target("avx2") //#pragma GCC target("sse4") #define all(v) v.begin(),v.end() #define F first #define S second #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front //#define randi uniform_int_distribution<long long> #define damoon(v) v.resize(unique(all(v))-v.begin()) //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //randi dist(0,10000000000000000); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<int,bool> pib; typedef pair<long long,bool> plb; typedef pair<int,pii> pip; typedef pair<pii,int> ppi; typedef vector<int> veci; typedef vector<long long> vecl; typedef vector<bool> vecb; typedef vector<pii> vecp; typedef set<int> seti; typedef set<long long> setl; typedef set<pii> setp; typedef map<int,int> mapii; typedef map<long long,long long> mapll; typedef map<int,bool> mapib; typedef map<long long,bool> maplb; const int mod=1e9+7,neginf=-1e9; const ll inf=1e15; const double PI=acos(-1); struct Segment { int N; struct Node { ll mn,lz; Node() { mn=lz=0; } }; vector<Node> t; Segment(int n) { N=n; t.resize(4*N); } void apply(int id,ll v) { t[id].mn+=v; t[id].lz+=v; } void push(int id) { if(t[id].lz==0) return; apply(2*id+0,t[id].lz); apply(2*id+1,t[id].lz); t[id].lz=0; } void pull(int id) { t[id].mn=min(t[2*id+0].mn,t[2*id+1].mn); } void update(int id,int L,int R,int l,int r,ll v) { if(r<=L or R<=l) return; if(l<=L and R<=r) { apply(id,v); return; } push(id); int mid=(L+R)>>1; update(2*id+0,L,mid,l,r,v); update(2*id+1,mid,R,l,r,v); pull(id); } ll get(int id,int L,int R,int l,int r) { if(r<=L or R<=l) return inf; if(l<=L and R<=r) return t[id].mn; push(id); int mid=(L+R)>>1; return min(get(2*id+0,L,mid,l,r),get(2*id+1,mid,R,l,r)); } void update(int l,int r,ll v) { update(1,1,N+1,l,r,v); } ll get(int l,int r) { return get(1,1,N+1,l,r); } }; int fposr(Segment &seg,ll x,int id,int L,int R) { if(L+1==R) return L; seg.push(id); int mid=(L+R)>>1; if(-seg.t[2*id].mn<x) return fposr(seg,x,2*id+1,mid,R); else return fposr(seg,x,2*id+0,L,mid); } int FP(Segment &seg,ll x) { return fposr(seg,x,1,1,seg.N+1); } void solve() { int n,m,q; cin>>n>>m>>q; veci t(q+1),a(q+1),b(q+1); vecl c(q+1),k(q+1),bb(q+1); vector<veci> opn(n+2),cls(n+2),qls(n+2); for(int i=1;i<=q;i++) { cin>>t[i]>>a[i]>>b[i]; if(t[i]==1) { cin>>c[i]>>k[i]; opn[a[i]].pub(i); cls[b[i]].pub(i); } else if(t[i]==2) { cin>>k[i]; opn[a[i]].pub(i); cls[b[i]].pub(i); } else { qls[a[i]].pub(i); bb[i]=b[i]; } } Segment Seg0(q),Seg1(q); veci ansind(q+1,0); for(int i=1;i<=n;i++) { for(int ind:opn[i]) { if(t[ind]==1) { Seg0.update(ind,q+1,+k[ind]); Seg1.update(ind,q+1,-k[ind]); } else { Seg0.update(ind,q+1,-k[ind]); } } for(int qi:qls[i]) { ll cur=Seg0.get(qi,qi+1); ll bst=Seg0.get(1,qi+1); ll res=cur-min(0LL,bst); ll ned=-Seg1.get(qi,qi+1)-res+bb[qi]; if(bb[qi]>res) { ansind[qi]=0; } else { ansind[qi]=FP(Seg1,ned); } } for(int ind:cls[i]) { if(t[ind]==1) { Seg0.update(ind,q+1,-k[ind]); Seg1.update(ind,q+1,+k[ind]); } else { Seg0.update(ind,q+1,+k[ind]); } } } for(int i=1;i<=q;i++) if(t[i]==3) cout<<(ansind[i]?c[ansind[i]]:0)<<"\n"; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); //ifstream fin("in.txt"); //ofstream fout("out.txt"); int t=1; //cin>>t; while(t--) { solve(); } }
#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...