oj.uz

Submission #83329

# Submission time Handle Problem Language Result Execution time Memory
83329 2018-11-07T03:18:23 Z Nordway Simple game (IZhO17_game) C++14
100 / 100
 584 ms 35196 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define boost ios_base::sync_with_stdio(0),cin.tie(0),cout.tie()

using namespace std;

typedef unsigned long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;

const ll INF = 1e18;
const int inf = INT_MAX;
const ll mod = 1e9 + 7;
const int pi = acos(-1);
const int dx[4] = {0, 1, 0, 0};
const int dy[4] = {1, 0, 0, 0};
const int N = 1e5 + 5;
const int MAXN = 1e6 + 1;
int t[4 * MAXN], a[N], z[4 * MAXN];

void push(int v, int tl, int tr){
	if(z[v]){
		if(tl != tr){
			z[v * 2] += z[v];
			z[v * 2 + 1] += z[v];
		}
		t[v] += z[v];
		z[v] = 0;
	}
}

void upd(int v, int tl, int tr, int l, int r, int val){
	if(tl > r || l > tr)return;
	if(l <= tl && tr <= r){
		z[v] += val;
		push(v, tl, tr);
		return ;
	}
	push(v, tl, tr);
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, val);
	upd(v * 2 + 1, tm + 1, tr, l, r, val);
	t[v] = t[v * 2] + t[v * 2 + 1];
}

int get(int v, int tl, int tr, int pos){
	push(v, tl, tr);
	if(tl == tr)return t[v];
	int tm = (tl + tr) / 2;
	if(pos <= tm)return get(v * 2, tl, tm, pos);
	else return get(v * 2 + 1, tm + 1, tr, pos);
}

int main(){
	//freopen("game.in", "r", stdin);
	//freopen("game.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(i > 1){
			upd(1, 1, 1e6, min(a[i], a[i - 1]), max(a[i], a[i - 1]), 1);
		}
	}
	while(m--){
		int type, h, pos, val;
		cin >> type;
		if(type == 1){
			cin >> pos >> val;
			if(pos != 1)upd(1, 1, 1e6, min(a[pos], a[pos - 1]), max(a[pos], a[pos - 1]), -1);
			if(pos != n)upd(1, 1, 1e6, min(a[pos], a[pos + 1]), max(a[pos], a[pos + 1]), -1);
			a[pos] = val;
			if(pos != 1)upd(1, 1, 1e6, min(a[pos], a[pos - 1]), max(a[pos], a[pos - 1]), 1);
			if(pos != n)upd(1, 1, 1e6, min(a[pos], a[pos + 1]), max(a[pos], a[pos + 1]), 1);
		}
		else{
			cin >> h;
			cout << get(1, 1, 1e6, h) << endl;
		}
	}
	
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 18 ms 15116 KB Output is correct
3 Correct 24 ms 15116 KB Output is correct
4 Correct 18 ms 15116 KB Output is correct
5 Correct 18 ms 15268 KB Output is correct
6 Correct 18 ms 15292 KB Output is correct
7 Correct 16 ms 15292 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 18 ms 15116 KB Output is correct
3 Correct 24 ms 15116 KB Output is correct
4 Correct 18 ms 15116 KB Output is correct
5 Correct 18 ms 15268 KB Output is correct
6 Correct 18 ms 15292 KB Output is correct
7 Correct 16 ms 15292 KB Output is correct
8 Correct 269 ms 15292 KB Output is correct
9 Correct 460 ms 20624 KB Output is correct
10 Correct 433 ms 22416 KB Output is correct
11 Correct 264 ms 22416 KB Output is correct
12 Correct 336 ms 22416 KB Output is correct
13 Correct 342 ms 25900 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 18 ms 15116 KB Output is correct
3 Correct 24 ms 15116 KB Output is correct
4 Correct 18 ms 15116 KB Output is correct
5 Correct 18 ms 15268 KB Output is correct
6 Correct 18 ms 15292 KB Output is correct
7 Correct 16 ms 15292 KB Output is correct
8 Correct 269 ms 15292 KB Output is correct
9 Correct 460 ms 20624 KB Output is correct
10 Correct 433 ms 22416 KB Output is correct
11 Correct 264 ms 22416 KB Output is correct
12 Correct 336 ms 22416 KB Output is correct
13 Correct 342 ms 25900 KB Output is correct
14 Correct 546 ms 27452 KB Output is correct
15 Correct 584 ms 29292 KB Output is correct
16 Correct 546 ms 31336 KB Output is correct
17 Correct 567 ms 33344 KB Output is correct
18 Correct 561 ms 35196 KB Output is correct