oj.uz

답안 #333898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333898 2020-12-08T02:35:55 Z tengiz05 Simple game (IZhO17_game) C++17
100 / 100
 139 ms 17644 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 1e6+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int a[N], n, m, k;
int t[N*2];
int mx = 1e6+3;
int query(int p){
	int ans = 0;
	for(p+=mx;p>0;p>>=1)ans += t[p];
	return ans;
}
void update(int l, int r, int val){
	for(l += mx, r += mx; l <= r; l>>=1, r>>=1){
		if(l%2 == 1)t[l++] += val;
		if(r%2 == 0)t[r--] += val;
	}
}
void show(){
	for(int i=0;i<mx;i++)cout << t[i] << ' ';
	cout << '\n';
	
	for(int i=0;i<mx;i++)cout << t[i+mx] << ' ';
	cout << '\n';
	
}
void solve(int test_case){
	int i, j;
	cin >> n >> m;
	for(i=0;i<n;i++){
		cin >> a[i];
	}
//	update(min(a[0], a[1]), max(a[0], a[1]), 1);
	for(i=1;i<n;i++){
		update(min(a[i], a[i-1]), max(a[i], a[i-1]), 1);
	}
	while(m--){
		int typ;
		cin >> typ;
		if(typ == 1){
			//update
			int pos, val;
			cin >> pos >> val;pos--;
			if(pos != 0){
				update(min(a[pos], a[pos-1]), max(a[pos], a[pos-1]), -1);
			}
			if(pos != n-1){
				update(min(a[pos], a[pos+1]), max(a[pos], a[pos+1]), -1);
			}
			a[pos] = val;
			if(pos != 0){
				update(min(a[pos], a[pos-1]), max(a[pos], a[pos-1]), 1);
			}
			if(pos != n-1){
				update(min(a[pos], a[pos+1]), max(a[pos], a[pos+1]), 1);
			}
			
		}else {
			//query
			int h;
			cin >> h;
			cout << query(h) << '\n';
		}
	}
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

game.cpp: In function 'void solve(long long int)':
game.cpp:37:9: warning: unused variable 'j' [-Wunused-variable]
   37 |  int i, j;
      |         ^

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 9580 KB Output is correct
3 Correct 7 ms 9196 KB Output is correct
4 Correct 7 ms 9324 KB Output is correct
5 Correct 7 ms 9324 KB Output is correct
6 Correct 7 ms 9324 KB Output is correct
7 Correct 2 ms 492 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 9580 KB Output is correct
3 Correct 7 ms 9196 KB Output is correct
4 Correct 7 ms 9324 KB Output is correct
5 Correct 7 ms 9324 KB Output is correct
6 Correct 7 ms 9324 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 37 ms 1388 KB Output is correct
9 Correct 87 ms 17388 KB Output is correct
10 Correct 87 ms 17644 KB Output is correct
11 Correct 32 ms 1388 KB Output is correct
12 Correct 51 ms 2304 KB Output is correct
13 Correct 46 ms 1772 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 9580 KB Output is correct
3 Correct 7 ms 9196 KB Output is correct
4 Correct 7 ms 9324 KB Output is correct
5 Correct 7 ms 9324 KB Output is correct
6 Correct 7 ms 9324 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 37 ms 1388 KB Output is correct
9 Correct 87 ms 17388 KB Output is correct
10 Correct 87 ms 17644 KB Output is correct
11 Correct 32 ms 1388 KB Output is correct
12 Correct 51 ms 2304 KB Output is correct
13 Correct 46 ms 1772 KB Output is correct
14 Correct 134 ms 17132 KB Output is correct
15 Correct 134 ms 17132 KB Output is correct
16 Correct 131 ms 17132 KB Output is correct
17 Correct 134 ms 17132 KB Output is correct
18 Correct 139 ms 17132 KB Output is correct