Submission #48398

#	Time	Username	Problem	Language	Result	Execution time	Memory
48398		aleksami	Simple game (IZhO17_game)	C++14	100 / 100	512 ms	35412 KiB

game

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXH 1000005

int tree[4*MAXH];
int lazy[4*MAXH];
int a[MAXN];

void push(int node,int left,int right)
{
	if(lazy[node]!=0)
	{
		tree[node]+=lazy[node]*(right-left+1);
		if(left != right)
		{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
}
void update(int node,int left,int right,int l,int r,int val)
{
	push(node,left,right);
	if(left >= l && right <= r)
	{
		lazy[node]+=val;
		push(node,left,right);
		return ;
	}
	int mid=(left+right)>>1;
	if(l <= mid)update(node*2,left,mid,l,r,val);
	if(r > mid)update(node*2+1,mid+1,right,l,r,val);
	tree[node]=tree[node*2]+tree[node*2+1];
}
int query(int node,int left,int right,int l,int r)
{
	push(node,left,right);
	if(left >= l && right <= r)return tree[node];
	int mid=(left+right)>>1;
	int ret=0;
	if(l <= mid)ret += query(node*2,left,mid,l,r);
	if(r > mid)ret += query(node*2+1,mid+1,right,l,r);
	return ret;
}


int main() {
	ios_base::sync_with_stdio(false);
	int n,q;
	cin >> n >> q;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for(int i = 0; i < n-1; i++)
	{
		int l = min(a[i],a[i+1]);
		int r = max(a[i],a[i+1]);
		if(l!=r)update(1,1,MAXH-1,l,r,1);
		else update(1,1,MAXH-1,l,r,2);
	}
	while(q--)
	{
		int t;
		cin >> t;
		if(t==1)
		{
			int pos,val;
			cin >> pos >> val;
			pos--;
			if(pos > 0)
            {
              if(a[pos-1]!=a[pos])update(1,1,MAXH-1,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),-1);
              else update(1,1,MAXH-1,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),-2);
            }
          	if(pos < n-1)
            {
              if(a[pos+1]!=a[pos])update(1,1,MAXH-1,min(a[pos+1],a[pos]),max(a[pos+1],a[pos]),-1);
              else update(1,1,MAXH-1,min(a[pos+1],a[pos]),max(a[pos+1],a[pos]),-2);
            }
          a[pos]=val;
          if(pos > 0)
            {
              if(a[pos-1]!=a[pos])update(1,1,MAXH-1,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),+1);
              else update(1,1,MAXH-1,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),+2);
            }
          	if(pos < n-1)
            {
              if(a[pos+1]!=a[pos])update(1,1,MAXH-1,min(a[pos+1],a[pos]),max(a[pos+1],a[pos]),+1);
              else update(1,1,MAXH-1,min(a[pos+1],a[pos]),max(a[pos+1],a[pos]),+2);
            }
		}
		else
		{
			int h;
			cin >> h;
			cout << query(1,1,MAXH-1,h,h) << "\n";
		}
	}
	return 0;
}

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