oj.uz

Submission #499682

# Submission time Handle Problem Language Result Execution time Memory
499682 2021-12-29T08:40:43 Z beksultan04 Simple game (IZhO17_game) C++14
100 / 100
 403 ms 30424 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define pii pair<int,int>
#define ret return
#define fr first
#define sc second
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define nosol puts("-1");
#define pb push_back
#define endi puts("");
#define ordered_set tree <int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N = 5e6+12,INF = 1e9+7;
int a[N],n,der[N],b[N],lp[N];
 
void push(int v,int l,int r){
	if (l == r){
		der[v] += lp[v];
		lp[v] = 0;
	}
	else {
		lp[v<<1] += lp[v];
		lp[v<<1|1] += lp[v];
		lp[v] = 0;
	}
}
 
void update(int v,int l,int r,int ql,int qr,int x){
	if (r < ql || qr < l){
		push(v,l,r);
		ret ;
	}
	if (ql <= l && r <= qr){
		lp[v] += x;
		push(v,l,r);
		ret ;
	}
	push(v,l,r);
	int m = l+r>>1;
	update(v<<1,l,m,ql,qr,x);
	update(v<<1|1,m+1,r,ql,qr,x);
}
 
int get_ans(int v,int l,int r,int pos){
	push(v,l,r);
	if (l == r){
		ret der[v]+lp[v];
	}
	int m = l+r>>1;
	if (m < pos)
		ret get_ans(v<<1|1,m+1,r,pos);
	else ret get_ans(v<<1,l,m,pos);
	
}
 
main(){
	int n,m,i,j;
	cin>>n>>m;
	
	for (i=1;i<=n;++i){
		cin>>a[i];
	}
	for (i=2;i<=n;++i)
		update(1,1,1000000,min(a[i],a[i-1]),max(a[i],a[i-1]),1);
		
		
	while (m--){
		int t;
		cin>>t;
		if (t == 2){
			int x;
			cin>>x;
			cout <<get_ans(1,1,1000000,x)<<"\n";
		}
		else {
			int pos,x;
			cin>>pos>>x;
			if (pos > 1){
				update(1,1,1000000,min(a[pos],a[pos-1]),max(a[pos],a[pos-1]),-1);
			}
			if (pos < n){
				update(1,1,1000000,min(a[pos],a[pos+1]),max(a[pos],a[pos+1]),-1);
			}
			a[pos] = x;
			
			if (pos > 1){
				update(1,1,1000000,min(a[pos],a[pos-1]),max(a[pos],a[pos-1]),1);
			}
			if (pos < n){
				update(1,1,1000000,min(a[pos],a[pos+1]),max(a[pos],a[pos+1]),1);
			}
		}
	}
	
}

Compilation message

game.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
game.cpp:46:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int m = l+r>>1;
      |          ~^~
game.cpp: In function 'long long int get_ans(long long int, long long int, long long int, long long int)':
game.cpp:56:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |  int m = l+r>>1;
      |          ~^~
game.cpp: At global scope:
game.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main(){
      | ^~~~
game.cpp: In function 'int main()':
game.cpp:64:12: warning: unused variable 'j' [-Wunused-variable]
   64 |  int n,m,i,j;
      |            ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 13 ms 17696 KB Output is correct
3 Correct 10 ms 17116 KB Output is correct
4 Correct 10 ms 17484 KB Output is correct
5 Correct 11 ms 17660 KB Output is correct
6 Correct 10 ms 17484 KB Output is correct
7 Correct 8 ms 12812 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 13 ms 17696 KB Output is correct
3 Correct 10 ms 17116 KB Output is correct
4 Correct 10 ms 17484 KB Output is correct
5 Correct 11 ms 17660 KB Output is correct
6 Correct 10 ms 17484 KB Output is correct
7 Correct 8 ms 12812 KB Output is correct
8 Correct 234 ms 1280 KB Output is correct
9 Correct 289 ms 30392 KB Output is correct
10 Correct 317 ms 30424 KB Output is correct
11 Correct 204 ms 1432 KB Output is correct
12 Correct 233 ms 2504 KB Output is correct
13 Correct 238 ms 30340 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 13 ms 17696 KB Output is correct
3 Correct 10 ms 17116 KB Output is correct
4 Correct 10 ms 17484 KB Output is correct
5 Correct 11 ms 17660 KB Output is correct
6 Correct 10 ms 17484 KB Output is correct
7 Correct 8 ms 12812 KB Output is correct
8 Correct 234 ms 1280 KB Output is correct
9 Correct 289 ms 30392 KB Output is correct
10 Correct 317 ms 30424 KB Output is correct
11 Correct 204 ms 1432 KB Output is correct
12 Correct 233 ms 2504 KB Output is correct
13 Correct 238 ms 30340 KB Output is correct
14 Correct 365 ms 30068 KB Output is correct
15 Correct 376 ms 30088 KB Output is correct
16 Correct 396 ms 30168 KB Output is correct
17 Correct 352 ms 30092 KB Output is correct
18 Correct 403 ms 30144 KB Output is correct