oj.uz

Submission #348733

# Submission time Handle Problem Language Result Execution time Memory
348733 2021-01-15T15:40:19 Z Sho10 Simple (info1cup19_simple) C++14
100 / 100
 687 ms 32748 KB 
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long 
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define aint(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,q,a[200005],lazy[1000005];
pair<ll,ll>mx[1000005],mn[1000005];



void build(ll node,ll l,ll r){
	if(l==r){
		if(a[l]%2==1){
			mx[node].f=-1;
			mx[node].s=a[l];
			mn[node].f=LINF-1;
			mn[node].s=a[l];
		}else {
			mx[node].f=a[l];
			mx[node].s=-1;
			mn[node].f=a[l];
			mn[node].s=LINF-1;
		}
		return;
	}
	ll mid=(l+r)/2;
	build(2*node,l,mid);
	build(2*node+1,mid+1,r);
	mx[node].f=max(mx[2*node].f,mx[2*node+1].f);
	mx[node].s=max(mx[2*node].s,mx[2*node+1].s);
	mn[node].f=min(mn[2*node].f,mn[2*node+1].f);
	mn[node].s=min(mn[2*node].s,mn[2*node+1].s);
}



void update(ll node,ll l,ll r,ll st,ll dr,ll val){
	if(l>r){
		return;
	}
	if(lazy[node]!=0){
		if(mn[node].f!=LINF-1){
			mn[node].f+=lazy[node];
		}
		if(mn[node].s!=LINF-1){
			mn[node].s+=lazy[node];
		}
		if(mx[node].f!=-1){
			mx[node].f+=lazy[node];
		}
		if(mx[node].s!=-1){
			mx[node].s+=lazy[node];
		}
		if(lazy[node]%2==1){
			swap(mn[node].f,mn[node].s);
			swap(mx[node].f,mx[node].s);
		}
		if(l!=r){
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	if(l>dr){
		return;
	}
	if(r<st){
		return;
	}
	if(st<=l&&r<=dr){
		lazy[node]+=val;
		if(mn[node].f!=LINF-1){
			mn[node].f+=lazy[node];
		}
		if(mn[node].s!=LINF-1){
			mn[node].s+=lazy[node];
		}
		if(mx[node].f!=-1){
			mx[node].f+=lazy[node];
		}
		if(mx[node].s!=-1){
			mx[node].s+=lazy[node];
		}
		if(lazy[node]%2==1){
			swap(mn[node].f,mn[node].s);
			swap(mx[node].f,mx[node].s);
		}
		if(l!=r){
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
		}
		lazy[node]=0;
		return;
	}
	ll mid=(l+r)/2;
	update(2*node,l,mid,st,dr,val);
	update(2*node+1,mid+1,r,st,dr,val);
	mn[node].f=min(mn[2*node].f,mn[2*node+1].f);
	mn[node].s=min(mn[2*node].s,mn[2*node+1].s);
	mx[node].f=max(mx[2*node].f,mx[2*node+1].f);
	mx[node].s=max(mx[2*node].s,mx[2*node+1].s);
	return;
}



ll query1(ll node,ll l,ll r,ll st,ll dr){
	if(l>r){
		return LINF-1;
	}
	if(lazy[node]!=0){
		if(mn[node].f!=LINF-1){
			mn[node].f+=lazy[node];
		}
		if(mn[node].s!=LINF-1){
			mn[node].s+=lazy[node];
		}
		if(mx[node].f!=-1){
			mx[node].f+=lazy[node];
		}
		if(mx[node].s!=-1){
			mx[node].s+=lazy[node];
		}
		if(lazy[node]%2==1){
			swap(mn[node].f,mn[node].s);
			swap(mx[node].f,mx[node].s);
		}
		if(l!=r){
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	if(l>dr){
		return LINF-1;
	}
	if(r<st){
		return LINF-1;
	}
	if(st<=l&&r<=dr){
		return mn[node].f;
	}
	ll mid=(l+r)/2;
ll s1=query1(2*node,l,mid,st,dr);
ll s2=query1(2*node+1,mid+1,r,st,dr);
mn[node].f=min(mn[2*node].f,mn[2*node+1].f);
	mn[node].s=min(mn[2*node].s,mn[2*node+1].s);
	mx[node].f=max(mx[2*node].f,mx[2*node+1].f);
	mx[node].s=max(mx[2*node].s,mx[2*node+1].s);
	return min(s1,s2);
}



ll query2(ll node,ll l,ll r,ll st,ll dr){
	if(l>r){
	return -1;
}
if(lazy[node]!=0){
		if(mn[node].f!=LINF-1){
			mn[node].f+=lazy[node];
		}
		if(mn[node].s!=LINF-1){
			mn[node].s+=lazy[node];
		}
		if(mx[node].f!=-1){
			mx[node].f+=lazy[node];
		}
		if(mx[node].s!=-1){
			mx[node].s+=lazy[node];
		}
		if(lazy[node]%2==1){
			swap(mn[node].f,mn[node].s);
			swap(mx[node].f,mx[node].s);
		}
		if(l!=r){
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	if(l>dr){
		return -1;
	}
	if(r<st){
		return -1;
	}
	if(st<=l&&r<=dr){
		return mx[node].s;
	}
	ll mid=(l+r)/2;
ll s1=query2(2*node,l,mid,st,dr);
ll s2=query2(2*node+1,mid+1,r,st,dr);
mn[node].f=min(mn[2*node].f,mn[2*node+1].f);
	mn[node].s=min(mn[2*node].s,mn[2*node+1].s);
	mx[node].f=max(mx[2*node].f,mx[2*node+1].f);
	mx[node].s=max(mx[2*node].s,mx[2*node+1].s);
	return max(s1,s2);
}	
int32_t main(){
CODE_START;
cin>>n;
for(ll i=1;i<=n;i++)
{
	cin>>a[i];
}
build(1,1,n);
cin>>q;
while(q--){
	ll type;
	cin>>type;
	if(type==0){
		ll l,r,val;
		cin>>l>>r>>val;
		update(1,1,n,l,r,val);
	}else {
		ll l,r;
		cin>>l>>r;
		update(1,1,n,l,r,0);
		ll s1=query1(1,1,n,l,r);
		if(s1==LINF-1){
		    s1=-1;
		}
		cout<<s1<<' ';
		s1=query2(1,1,n,l,r);
		if(s1==0){
		    s1=-1;
		}
		cout<<s1<<endl;
	}
}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 748 KB Output is correct
2 Correct 8 ms 876 KB Output is correct
3 Correct 10 ms 1260 KB Output is correct
4 Correct 11 ms 1260 KB Output is correct
5 Correct 10 ms 1260 KB Output is correct
6 Correct 10 ms 1260 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 13292 KB Output is correct
2 Correct 686 ms 25984 KB Output is correct
3 Correct 681 ms 26092 KB Output is correct
4 Correct 675 ms 25964 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 748 KB Output is correct
2 Correct 8 ms 876 KB Output is correct
3 Correct 10 ms 1260 KB Output is correct
4 Correct 11 ms 1260 KB Output is correct
5 Correct 10 ms 1260 KB Output is correct
6 Correct 10 ms 1260 KB Output is correct
7 Correct 303 ms 13292 KB Output is correct
8 Correct 686 ms 25984 KB Output is correct
9 Correct 681 ms 26092 KB Output is correct
10 Correct 675 ms 25964 KB Output is correct
11 Correct 308 ms 16108 KB Output is correct
12 Correct 678 ms 31468 KB Output is correct
13 Correct 682 ms 32236 KB Output is correct
14 Correct 671 ms 31596 KB Output is correct
15 Correct 687 ms 32748 KB Output is correct
16 Correct 119 ms 24812 KB Output is correct