Submission #230009

#TimeUsernameProblemLanguageResultExecution timeMemory
230009Tenis0206Simple (info1cup19_simple)C++11
30 / 100
296 ms17936 KiB
#include <bits/stdc++.h> using namespace std; int n,q,ai1[1000005],ai2[1000005],ai3[1000005],ai4[1000005],lazy[1000005],v[200005]; const int oo = INT_MAX; void propag(int nod, int a, int b) { if(a==b || lazy[nod]==0) return; lazy[nod*2]+=lazy[nod]; lazy[nod*2+1]+=lazy[nod]; if(ai1[nod*2]!=oo) ai1[nod*2]+=lazy[nod]; if(ai1[nod*2+1]!=oo) ai1[nod*2+1]+=lazy[nod]; if(ai2[nod*2]!=oo) ai2[nod*2]+=lazy[nod]; if(ai2[nod*2+1]!=oo) ai2[nod*2+1]+=lazy[nod]; if(ai3[nod*2]!=-oo) ai3[nod*2]+=lazy[nod]; if(ai3[nod*2+1]!=-oo) ai3[nod*2+1]+=lazy[nod]; if(ai4[nod*2]!=-oo) ai4[nod*2]+=lazy[nod]; if(ai4[nod*2+1]!=-oo) ai4[nod*2+1]+=lazy[nod]; if(lazy[nod]%2) { swap(ai1[nod*2],ai2[nod*2]); swap(ai1[nod*2+1],ai2[nod*2+1]); swap(ai3[nod*2],ai4[nod*2]); swap(ai4[nod*2+1],ai4[nod*2+1]); } lazy[nod]=0; } void update(int ua, int ub, int val, int nod, int a, int b) { if(ua<=a && ub>=b) { lazy[nod]+=val; if(ai1[nod]!=oo) ai1[nod]+=val; if(ai2[nod]!=oo) ai2[nod]+=val; if(ai3[nod]!=-oo) ai3[nod]+=val; if(ai4[nod]!=-oo) ai4[nod]+=val; if(val%2) { swap(ai1[nod],ai2[nod]); swap(ai3[nod],ai4[nod]); } return; } propag(nod,a,b); int mij=(a+b)/2; if(ua<=mij) { update(ua,ub,val,nod*2,a,mij); } if(ub>mij) { update(ua,ub,val,nod*2+1,mij+1,b); } ai1[nod]=min(ai1[nod*2],ai1[nod*2+1]); ai2[nod]=min(ai2[nod*2],ai2[nod*2+1]); ai3[nod]=max(ai3[nod*2],ai3[nod*2+1]); ai4[nod]=max(ai4[nod*2],ai4[nod*2+1]); } pair<int,int> query(int qa, int qb, int nod, int a, int b) { if(qa<=a && qb>=b) { return {ai1[nod],ai3[nod]}; } propag(nod,a,b); int mij=(a+b)/2; pair<int,int> rez1={oo,-oo},rez2={oo,-oo}; if(qa<=mij) { rez1=query(qa,qb,nod*2,a,mij); } if(qb>mij) { rez2=query(qa,qb,nod*2+1,mij+1,b); } return {min(rez1.first,rez2.first),max(rez1.second,rez2.second)}; } void update_in(int poz, int val, int nod, int a, int b) { if(a==b) { if(val%2==0) { ai1[nod]=ai4[nod]=val; ai2[nod]=oo; ai3[nod]=-oo; } else if(val%2==1) { ai2[nod]=ai3[nod]=val; ai1[nod]=oo; ai4[nod]=-oo; } return; } int mij=(a+b)/2; if(poz<=mij) { update_in(poz,val,nod*2,a,mij); } else { update_in(poz,val,nod*2+1,mij+1,b); } ai1[nod]=min(ai1[nod*2],ai1[nod*2+1]); ai2[nod]=min(ai2[nod*2],ai2[nod*2+1]); ai3[nod]=max(ai3[nod*2],ai3[nod*2+1]); ai4[nod]=max(ai4[nod*2],ai4[nod*2+1]); } int main() { ///1 for minimum even number ///2 for minimum odd number ///3 for maximum odd number ///4 for maximum even number ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=1;i<=n;i++) { cin>>v[i]; update_in(i,v[i],1,1,n); } cin>>q; for(int i=1;i<=q;i++) { int t,a,b,val; cin>>t; if(t==0) { cin>>a>>b>>val; update(a,b,val,1,1,n); } else if(t==1) { cin>>a>>b; pair<int,int> rez=query(a,b,1,1,n); if(rez.first==oo) { cout<<-1<<' '; } else { cout<<rez.first<<' '; } if(rez.second==-oo) { cout<<-1<<'\n'; } else { cout<<rez.second<<'\n'; } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...