oj.uz

Submission #174689

# Submission time Handle Problem Language Result Execution time Memory
174689 2020-01-06T17:06:19 Z Gurban Simple game (IZhO17_game) C++14
100 / 100
 481 ms 44152 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 29 ms 19832 KB Output is correct
3 Correct 28 ms 19448 KB Output is correct
4 Correct 30 ms 19980 KB Output is correct
5 Correct 29 ms 19704 KB Output is correct
6 Correct 29 ms 19796 KB Output is correct
7 Correct 20 ms 14556 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 29 ms 19832 KB Output is correct
3 Correct 28 ms 19448 KB Output is correct
4 Correct 30 ms 19980 KB Output is correct
5 Correct 29 ms 19704 KB Output is correct
6 Correct 29 ms 19796 KB Output is correct
7 Correct 20 ms 14556 KB Output is correct
8 Correct 103 ms 1796 KB Output is correct
9 Correct 268 ms 44024 KB Output is correct
10 Correct 267 ms 44088 KB Output is correct
11 Correct 100 ms 1656 KB Output is correct
12 Correct 148 ms 3956 KB Output is correct
13 Correct 180 ms 43924 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 29 ms 19832 KB Output is correct
3 Correct 28 ms 19448 KB Output is correct
4 Correct 30 ms 19980 KB Output is correct
5 Correct 29 ms 19704 KB Output is correct
6 Correct 29 ms 19796 KB Output is correct
7 Correct 20 ms 14556 KB Output is correct
8 Correct 103 ms 1796 KB Output is correct
9 Correct 268 ms 44024 KB Output is correct
10 Correct 267 ms 44088 KB Output is correct
11 Correct 100 ms 1656 KB Output is correct
12 Correct 148 ms 3956 KB Output is correct
13 Correct 180 ms 43924 KB Output is correct
14 Correct 479 ms 43932 KB Output is correct
15 Correct 463 ms 44056 KB Output is correct
16 Correct 473 ms 44152 KB Output is correct
17 Correct 481 ms 44092 KB Output is correct
18 Correct 481 ms 44056 KB Output is correct