oj.uz

Submission #915496

# Submission time Handle Problem Language Result Execution time Memory
915496 2024-01-24T05:09:15 Z vjudge1 Simple game (IZhO17_game) C++17
0 / 100
 2 ms 2396 KB 
/*#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll n,m,k,cnt;
ll t[4000010],add[4000010];
ll a[1000010];
void push(ll v, ll tl, ll tr)
{
	if(add[v]!=0)
	{
		add[v+v]+=add[v];
		add[v+v+1]+=add[v];
		
		ll tm=(tl+tr)>>1;
		t[v+v]+=(tm-tl+1)*add[v];
		t[v+v+1]+=(tr-tm)*add[v];
		
		add[v]=0;
	}
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll val)
{
	//cout<<v<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<" "<<val<<"\n";
	if(tl>tr || l>r)
	{
		return;
	}
	if(tl==l && tr==r)
	{
		t[v]+=(tr-tl+1)*val;
		add[v]+=val;
		return;
	}
	push(v,tl,tr);
	ll tm=(tl+tr)>>1;
	upd(v+v,tl,tm,l,min(r,tm),val);
	upd(v+v+1,tm+1,tr,max(tm+1,l),r,val);
	t[v]=t[v+v]+t[v+v+1];
}
ll get(ll v,ll tl,ll tr,ll pos)
{
	if(tl==tr)
	{
		return t[v];
	}
	push(v,tl,tr);
	ll tm=(tl+tr)>>1;
	if(tm>=pos)
	{
		return get(v+v,tl,tm,pos);
	}
	else
	{
		return get(v+v+1,tm+1,tr,pos);
	}
}
void anomalous_solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<n;i++)
	{
		//cout<<min(a[i],a[i+1])<<" "<<max(a[i],a[i+1])<<"\n";
		upd(1,1,n,min(a[i],a[i+1]),max(a[i],a[i+1]),1);
	}
	//cout<<"-------------------------\n";
	ll tp,pos,val,h;
	while(m--)
	{
		cin>>tp;
		if(tp==1)
		{
			cin>>pos>>val;
			if(pos<n)upd(1,1,n,min(a[pos],a[pos+1]),max(a[pos],a[pos+1]),-1);
			if(pos>1)upd(1,1,n,min(a[pos],a[pos-1]),max(a[pos],a[pos-1]),-1);
			a[pos]=val;
			if(pos<n)upd(1,1,n,min(a[pos],a[pos+1]),max(a[pos],a[pos+1]),1);
			if(pos>1)upd(1,1,n,min(a[pos],a[pos-1]),max(a[pos],a[pos-1]),1);
		}
		else
		{
			cin>>h;
			cout<<get(1,1,n,h)<<"\n";
		}
	}
}
int main()
{
	//	freopen("INPUT.txt","r",stdin);
	//  freopen("OUTPUT.txt","w",stdout);

	ios_base::sync_with_stdio();
    cin.tie(NULL);
    cout.tie(NULL);

    ll test=1;
	//cin>>test;
    for(int pos=1;pos<=test;pos++)
    	anomalous_solve();
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -