oj.uz

Submission #499664

# Submission time Handle Problem Language Result Execution time Memory
499664 2021-12-29T07:48:12 Z beksultan04 Simple game (IZhO17_game) C++14
100 / 100
 333 ms 19776 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 update(int v,int l,int r,int ql,int qr,int x){
	if (r < ql || qr < l){
		ret ;
	}
	if (ql <= l && r <= qr){
		der[v] += x;
		ret ;
	}
	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){
	if (l == r){
		ret der[v];
	}
	int m = l+r>>1;
	if (m < pos)
		ret der[v] + get_ans(v<<1|1,m+1,r,pos);
	else ret der[v] + 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:31:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |  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:40:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  int m = l+r>>1;
      |          ~^~
game.cpp: At global scope:
game.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~
game.cpp: In function 'int main()':
game.cpp:48:12: warning: unused variable 'j' [-Wunused-variable]
   48 |  int n,m,i,j;
      |            ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 7 ms 9548 KB Output is correct
3 Correct 7 ms 9164 KB Output is correct
4 Correct 7 ms 9264 KB Output is correct
5 Correct 8 ms 9416 KB Output is correct
6 Correct 7 ms 9548 KB Output is correct
7 Correct 4 ms 316 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 7 ms 9548 KB Output is correct
3 Correct 7 ms 9164 KB Output is correct
4 Correct 7 ms 9264 KB Output is correct
5 Correct 8 ms 9416 KB Output is correct
6 Correct 7 ms 9548 KB Output is correct
7 Correct 4 ms 316 KB Output is correct
8 Correct 179 ms 2072 KB Output is correct
9 Correct 286 ms 19600 KB Output is correct
10 Correct 255 ms 19648 KB Output is correct
11 Correct 184 ms 2164 KB Output is correct
12 Correct 216 ms 3500 KB Output is correct
13 Correct 204 ms 3152 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 7 ms 9548 KB Output is correct
3 Correct 7 ms 9164 KB Output is correct
4 Correct 7 ms 9264 KB Output is correct
5 Correct 8 ms 9416 KB Output is correct
6 Correct 7 ms 9548 KB Output is correct
7 Correct 4 ms 316 KB Output is correct
8 Correct 179 ms 2072 KB Output is correct
9 Correct 286 ms 19600 KB Output is correct
10 Correct 255 ms 19648 KB Output is correct
11 Correct 184 ms 2164 KB Output is correct
12 Correct 216 ms 3500 KB Output is correct
13 Correct 204 ms 3152 KB Output is correct
14 Correct 296 ms 19704 KB Output is correct
15 Correct 287 ms 19776 KB Output is correct
16 Correct 333 ms 19648 KB Output is correct
17 Correct 290 ms 19616 KB Output is correct
18 Correct 305 ms 19652 KB Output is correct