Submission #85768

#	Time	Username	Problem	Language	Result	Execution time	Memory
85768		farukkastamonuda	Simple game (IZhO17_game)	C++14	100 / 100	570 ms	35184 KiB

game

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 100005
#define HOP 1000000
#define mid (start+end)/2
using namespace std;
int n,m,A[li],t,tree[HOP*4+5],lazy[HOP*4+5];
void push(int node,int start,int end){
	if(lazy[node]==0) return ;
	tree[node]+=lazy[node]*(end-start+1);
	if(start!=end){
		lazy[node*2]+=lazy[node];
		lazy[node*2+1]+=lazy[node];
	}
	lazy[node]=0;
}
void update(int node,int start,int end,int l,int r,int val){
	if(l>r) return ;
	push(node,start,end);
	if(start>end || start>r || end<l) return ;
	if(start>=l && end<=r){
		lazy[node]+=val;
		push(node,start,end);
		return ;
	}
	update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
	tree[node]=tree[node*2]+tree[node*2+1];
}
int q1(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l) return 0;
	push(node,start,end);
	if(start>=l && end<=r) return tree[node];
	return q1(node*2,start,mid,l,r)+q1(node*2+1,mid+1,end,l,r);
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&A[i]);
		if(i>1){
			int mn=min(A[i-1],A[i]);
			int mx=max(A[i-1],A[i]);
			update(1,1,HOP,mn+1,mx-1,1);
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%d",&t);
		if(t==2){
			int x;
			scanf("%d",&x);
			printf("%d\n",q1(1,1,HOP,x,x));
		}
		else{
			int pos,val;
			scanf("%d %d",&pos,&val);
			if(pos>1){
				int mn=min(A[pos-1],A[pos]);
				int mx=max(A[pos-1],A[pos]);
				update(1,1,HOP,mn+1,mx-1,-1);
			}
			if(pos<n){
				int mn=min(A[pos],A[pos+1]);
				int mx=max(A[pos],A[pos+1]);
				update(1,1,HOP,mn+1,mx-1,-1);
			}
			A[pos]=val;
			if(pos>1){
				int mn=min(A[pos-1],A[pos]);
				int mx=max(A[pos-1],A[pos]);
				update(1,1,HOP,mn+1,mx-1,1);
			}
			if(pos<n){
				int mn=min(A[pos],A[pos+1]);
				int mx=max(A[pos],A[pos+1]);
				update(1,1,HOP,mn+1,mx-1,1);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
game.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&A[i]);
   ~~~~~^~~~~~~~~~~~
game.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~
game.cpp:55:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~
game.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&pos,&val);
    ~~~~~^~~~~~~~~~~~~~~~~~~

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