Submission #231331

#TimeUsernameProblemLanguageResultExecution timeMemory
231331filiptudose7Simple (info1cup19_simple)C++11
30 / 100
300 ms27000 KiB
#include <bits/stdc++.h> using namespace std; long long n,q,ai1[1000005],ai2[1000005],ai3[1000005],ai4[1000005],lazy[1000005],v[200005]; const long long bignumber = 1LL*INT_MAX*INT_MAX; void propag(long long nod, long long a, long long b) { if(a==b || lazy[nod]==0) return; lazy[nod*2]+=lazy[nod]; lazy[nod*2+1]+=lazy[nod]; if(ai1[nod*2]!=bignumber) ai1[nod*2]+=lazy[nod]; if(ai1[nod*2+1]!=bignumber) ai1[nod*2+1]+=lazy[nod]; if(ai2[nod*2]!=bignumber) ai2[nod*2]+=lazy[nod]; if(ai2[nod*2+1]!=bignumber) ai2[nod*2+1]+=lazy[nod]; if(ai3[nod*2]!=-bignumber) ai3[nod*2]+=lazy[nod]; if(ai3[nod*2+1]!=-bignumber) ai3[nod*2+1]+=lazy[nod]; if(ai4[nod*2]!=-bignumber) ai4[nod*2]+=lazy[nod]; if(ai4[nod*2+1]!=-bignumber) 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(long long ua, long long ub, long long val, long long nod, long long a, long long b) { if(ua<=a && ub>=b) { lazy[nod]+=val; if(ai1[nod]!=bignumber) ai1[nod]+=val; if(ai2[nod]!=bignumber) ai2[nod]+=val; if(ai3[nod]!=-bignumber) ai3[nod]+=val; if(ai4[nod]!=-bignumber) ai4[nod]+=val; if(val%2) { swap(ai1[nod],ai2[nod]); swap(ai3[nod],ai4[nod]); } return; } propag(nod,a,b); long long 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<long long,long long> query(long long qa, long long qb, long long nod, long long a, long long b) { if(qa<=a && qb>=b) { return {ai1[nod],ai3[nod]}; } propag(nod,a,b); long long mij=(a+b)/2; pair<long long,long long> rez1={bignumber,-bignumber},rez2={bignumber,-bignumber}; 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(long long poz, long long val, long long nod, long long a, long long b) { if(a==b) { if(val%2==0) { ai1[nod]=ai4[nod]=val; ai2[nod]=bignumber; ai3[nod]=-bignumber; } else if(val%2==1) { ai2[nod]=ai3[nod]=val; ai1[nod]=bignumber; ai4[nod]=-bignumber; } return; } long long 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() { //freopen("in","r",stdin); //freopen("out","w",stdout); cin.sync_with_stdio(false); cin.tie(0); cin>>n; for(long long i=1;i<=n;i++) { cin>>v[i]; update_in(i,v[i],1,1,n); } cin>>q; for(long long i=1;i<=q;i++) { long long t,a,b,val; cin>>t; if(t==0) { cin>>a>>b>>val; if(a>b) continue; update(a,b,val,1,1,n); } else if(t==1) { cin>>a>>b; if(a>b) { cout<<"-1 -1"<<'\n'; } pair<long long,long long> rez=query(a,b,1,1,n); if(rez.first==bignumber) { cout<<-1<<' '; } else { cout<<rez.first<<' '; } if(rez.second==-bignumber) { 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...