Submission #174689

#	Time	Username	Problem	Language	Result	Execution time	Memory
174689		Gurban	Simple game (IZhO17_game)	C++14	100 / 100	481 ms	44152 KiB

game

#include <bits/stdc++.h>

#define pb push_back
#define ss second
#define ff first
#define N 100005
#define inf 1000000009
#define ll long long
#define mid(a,b) (a+b)/2
#define pii pair<int,int>

using namespace std;

const int H = 1e6+7;
int n,m,T[4 * H][5],a[N],pos,val,h,t;

void upd(int t,int a,int b,int l,int r,int nd){
	T[nd][0] += T[nd / 2][1];
	T[nd][0] -= T[nd / 2][2];
	T[nd][1] += T[nd / 2][1];
	T[nd][2] += T[nd / 2][2];
	if(l >= a and r <= b){
		if(t == 1) {
			T[nd][0] ++;
			T[nd][1] ++;
		}
		else {
			T[nd][0]--;
			T[nd][2]++;
		}
		return;
	}
	if(l > b or r < a)
		return;
	upd(t,a,b,l,mid(l,r),nd * 2);
	upd(t,a,b,mid(l,r) + 1,r,nd * 2 + 1);
	T[nd][1] = 0;
	T[nd][2] = 0;
	T[nd][0] = T[nd * 2][0] + T[nd * 2 + 1][0];
}

int tap(int h,int l,int r,int nd){
	if(l == r) return T[nd][0];
	T[nd * 2][0] += T[nd][1];
	T[nd * 2][0] -= T[nd][2];
	T[nd * 2][1] += T[nd][1];
	T[nd * 2][2] += T[nd][2];
	T[nd * 2 + 1][0] += T[nd][1];
	T[nd * 2 + 1][0] -= T[nd][2];
	T[nd * 2 + 1][1] += T[nd][1];
	T[nd * 2 + 1][2] += T[nd][2];
	T[nd][1] = 0;
	T[nd][2] = 0;
	if(h <= mid(l,r)) return tap(h,l,mid(l,r),nd * 2);
	else return tap(h,mid(l,r) + 1,r,nd * 2 + 1);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++){
		scanf("%d",a + i);
		if(i > 1) upd(1,min(a[i],a[i - 1]),max(a[i],a[i - 1]),1,H,1);
	}
	while(m--){
		scanf("%d",&t);
		if(t == 1){
			scanf("%d%d",&pos,&val);
			if(pos > 1) upd(2,min(a[pos],a[pos - 1]),max(a[pos],a[pos - 1]),1,H,1);
			if(pos < n) upd(2,min(a[pos],a[pos + 1]),max(a[pos],a[pos + 1]),1,H,1);
			a[pos] = val;
			if(pos > 1) upd(1,min(a[pos],a[pos - 1]),max(a[pos],a[pos - 1]),1,H,1);
			if(pos < n) upd(1,min(a[pos],a[pos + 1]),max(a[pos],a[pos + 1]),1,H,1);
		}
		if(t == 2){
			scanf("%d",&h);
			printf("%d\n",tap(h,1,H,1));
		}
	}
}
/*
3 3
1 5 1
2 3
1 1 5
2 3
*/

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:60: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:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a + i);
   ~~~~~^~~~~~~~~~~~
game.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~
game.cpp:68:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&pos,&val);
    ~~~~~^~~~~~~~~~~~~~~~~~
game.cpp:76:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&h);
    ~~~~~^~~~~~~~~

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