Submission #915503

#	Time	Username	Problem	Language	Result	Execution time	Memory
915503		vjudge1	Simple game (IZhO17_game)	C++17	0 / 100	0 ms	348 KiB

game

/*#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[100010];
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("game.in","r",stdin);
	freopen("game.out","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();
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:95:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  freopen("game.in","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
game.cpp:96:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  freopen("game.out","w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51