/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 324.0 KiB
#2 Accepted 2ms 320.0 KiB
#3 Accepted 564ms 2.812 MiB
#4 Accepted 536ms 8.105 MiB
#5 Accepted 457ms 6.945 MiB
#6 Accepted 360ms 2.32 MiB
#7 Accepted 1ms 532.0 KiB
#8 Accepted 1ms 316.0 KiB
#9 Accepted 758ms 8.457 MiB
#10 Accepted 681ms 9.953 MiB

Code

#include<bits/stdc++.h>
using namespace std;
using ll=long long int;

void show(auto x){ cout<<x<<"\n";}

///////////////////////////////////

int main()
{
	ll n;;cin>>n;
	
	vector<ll> v(n+1);
	
	for(int i=1;i<=n;i++)
	{
		cin>>v[i];
	}
	
	set<ll> st;
	
	for(int i=1;i<=n;i++)
	{
		if(i==1)
		{
			if(v[i]>v[i+1])
			{
				st.insert(i);
			}
		}
		else if(i==n)
		{
			if(v[i-1]>v[i])
			{
				st.insert(i);
			}
		}
		else
		{
			if(v[i-1]>v[i] || v[i]>v[i+1])
			{
				st.insert(i);
			}
		}
	}
	
	ll  q;cin>>q;
	
	while(q--)
	{
		ll x;cin>>x;
		
		if(x==1)
		{
			ll ind,val;cin>>ind>>val;
			
			st.erase(ind);
			
			v[ind]=val;
			
			ll a=max(1LL,ind-1);
			ll b=min(n,ind+1);
					
			for(ll i=a;i<=b;i++)
			{
				if(i==1)
				{
					if(v[i]<=v[i+1])
					{
						st.erase(i);
					}
					else
					{
						st.insert(i);
					}
				}
				else if(i==n)
				{
					if(v[i-1]<=v[i])
					{
						st.erase(i);
					}
					else
					{
						st.insert(i);
					}
				}
				else
				{
					if(v[i-1]<=v[i] && v[i]<=v[i+1])
					{
						st.erase(i);
					}
					else
					{
						st.insert(i);
					}
					
				}
			}
				
			
		}
		else
		{
			ll l,r;cin>>l>>r;
			
			auto it=st.lower_bound(l+1);
			
			auto it1=st.find(l);
			auto it2=st.find(r);
			
			int check1=0;
			int check2=0;
			
			if(*it1!=l)
			{
				check1=1;
			}
			if(*it2!=r)
			{
				check2=1;
			}
			if(*it1==l)
			{
				if(v[l]<=v[l+1])
				{
					check1=1;
				}
			}
			if(*it2==r)
			{
				if(v[r-1]<=v[r])
				{
					check2=1;
				}
			}
			
			
			if(l==r)
			{
				show("YES");
			}
			else
			{
				if(check1 && check2 && (it==st.end() || *it>=r))
				{
					show("YES");
				}
				else
				{
					show("NO");
				}
			}
		}
		
	
	}
	
	return 0;
} 

Information

Submit By
Type
Submission
Problem
P1085 Sorted or !Sorted
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-25 15:31:16
Judged At
2024-11-11 03:05:05
Judged By
Score
100
Total Time
758ms
Peak Memory
9.953 MiB