oj.uz

Submission #499812

# Submission time Handle Problem Language Result Execution time Memory
499812 2021-12-29T15:24:22 Z tmn2005 Simple game (IZhO17_game) C++17
100 / 100
 274 ms 19792 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define ar array
#define fr first
#define sc second

#define vec vector
#define ret return

#define ins insert
#define mk make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_back

#define int long long

#define pii pair<int,int>

#define all(s) s.begin(), s.end()
#define allr(s) s.rbegin(), s.rend()

#define NeedForSpeed ios::sync_with_stdio(0),cin.tie(0);
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N=1e6+12,INF=1e9,mod = 1e9+7;
bool iswowel(char n){ n = toupper(n); if(n == 'A' || n == 'O' || n == 'U' || n == 'E' || n == 'I') return true; else return false;}
int n,m,k,x,y,l,r,o,ans,res,ok,mx,mn = INF;
int a[N],b,c;
int t[N*4];

void update(int v,int l,int r,int ql,int qr,int add){
	if (r < ql || qr < l)
		ret;
	if(ql <= l && r <= qr)
		t[v] += add;
	else{
		int m = l + r >> 1;
		update(v*2,l,m,ql, min(m,qr),add);
		update(v*2+1,m+1,r,max(m+1,ql),qr,add);
	}
}
int get(int v,int l,int r,int i){
	if(l == r)
		ret t[v];
	int m = l + r >> 1;
	if(i <= m)
		ret t[v] + get(v*2,l,m,i);
	else
		ret t[v] + get(v*2+1,m+1,r,i);
}
main(){
	NeedForSpeed
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	
    cin>>n>>m;
    for(int i=1; i<=n; i++){
    	cin>>a[i];
	}
	for(int i=2; i<=n; i++){
    	update(1,1,1000000,min(a[i], a[i-1]), max(a[i], a[i-1]), 1);
	}
	while(m--){
		cin>>o;
		if(o == 1){
			int i;
			cin>>i>>x;
			if(1 < i){
				update(1, 1, 1000000, min(a[i-1], a[i]), max(a[i-1], a[i]), -1);
			}
			if(i < n){
				update(1, 1, 1000000, min(a[i+1], a[i]), max(a[i+1], a[i]), -1);
			}
			a[i] = x;
			if(1 < i){
				update(1, 1, 1000000, min(a[i-1], a[i]), max(a[i-1], a[i]), 1);
			}
			if(i < n){
				update(1, 1, 1000000, min(a[i+1], a[i]), max(a[i+1], a[i]), 1);
			}
		}
		else{
			cin>>x;
			cout<<get(1,1,1000000,x)<<endl;
		}
	}
	




	return 0;
}

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:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int m = l + r >> 1;
      |           ~~^~~
game.cpp: In function 'long long int get(long long int, long long int, long long int, long long int)':
game.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int m = l + r >> 1;
      |          ~~^~~
game.cpp: At global scope:
game.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main(){
      | ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9288 KB Output is correct
4 Correct 7 ms 9292 KB Output is correct
5 Correct 7 ms 9412 KB Output is correct
6 Correct 7 ms 9548 KB Output is correct
7 Correct 3 ms 328 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 7 ms 9676 KB Output is correct
3 Correct 7 ms 9288 KB Output is correct
4 Correct 7 ms 9292 KB Output is correct
5 Correct 7 ms 9412 KB Output is correct
6 Correct 7 ms 9548 KB Output is correct
7 Correct 3 ms 328 KB Output is correct
8 Correct 154 ms 2100 KB Output is correct
9 Correct 226 ms 19704 KB Output is correct
10 Correct 200 ms 19676 KB Output is correct
11 Correct 140 ms 1884 KB Output is correct
12 Correct 166 ms 3524 KB Output is correct
13 Correct 151 ms 3164 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 7 ms 9676 KB Output is correct
3 Correct 7 ms 9288 KB Output is correct
4 Correct 7 ms 9292 KB Output is correct
5 Correct 7 ms 9412 KB Output is correct
6 Correct 7 ms 9548 KB Output is correct
7 Correct 3 ms 328 KB Output is correct
8 Correct 154 ms 2100 KB Output is correct
9 Correct 226 ms 19704 KB Output is correct
10 Correct 200 ms 19676 KB Output is correct
11 Correct 140 ms 1884 KB Output is correct
12 Correct 166 ms 3524 KB Output is correct
13 Correct 151 ms 3164 KB Output is correct
14 Correct 243 ms 19792 KB Output is correct
15 Correct 252 ms 19652 KB Output is correct
16 Correct 248 ms 19612 KB Output is correct
17 Correct 274 ms 19620 KB Output is correct
18 Correct 264 ms 19788 KB Output is correct