oj.uz

Submission #505684

# Submission time Handle Problem Language Result Execution time Memory
505684 2022-01-11T06:50:05 Z pragmatist Simple game (IZhO17_game) C++17
100 / 100
 199 ms 19468 KB 
#include <bits/stdc++.h>                            
 
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define x first
#define y second
#define int long long
#define nl "\n"
 
using namespace std;
 
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair <ll, ll> pii;
 
const int N = (int)1e6 + 7;
const int M = (int)5e6 + 7;
const ll MOD = (ll)1e9 + 7;                    
const int inf = (int)1e9 + 7;
const ll INF = (ll)3e18 + 7;
 
pii dir[] = {{-1, -1}, {1, 1}, {-1, 1}, {1, -1}};
 
int n, q, y[N], t[4*N];

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

int get(int v, int tl, int tr, int id, int res) {
	res += t[v];
	if(tl == tr)
		return res;
	int mid = (tl + tr) >> 1;
	if(id <= mid)
		return get(v * 2, tl, mid, id, res);
	else
		return get(v * 2 + 1, mid + 1, tr, id, res);
}
 
void solve() {           
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		cin >> y[i];		
	}
	for(int i = 1; i < n; ++i) {
		int l = min(y[i], y[i + 1]), r = max(y[i], y[i + 1]);
		upd(1, 1, 1e6, l, r, 1);
	}
	while(q--) {
		char tp;
		cin >> tp;
		int i, d;
		if(tp == '1') {
			cin >> i >> d;
			if(i < n) {
				int l = min(y[i], y[i + 1]), r = max(y[i], y[i + 1]);
				upd(1, 1, 1e6, l, r, -1);
			}
			if(i > 1) {                  				
				int l = min(y[i], y[i - 1]), r = max(y[i], y[i - 1]);
				upd(1, 1, 1e6, l, r, -1);			
			}
			y[i] = d;
			if(i < n) {
				int l = min(y[i], y[i + 1]), r = max(y[i], y[i + 1]);
				upd(1, 1, 1e6, l, r, 1);
			}
			if(i > 1) {                  				
				int l = min(y[i], y[i - 1]), r = max(y[i], y[i - 1]);
				upd(1, 1, 1e6, l, r, 1);			
			}		
		} else {
			cin >> d;
			cout << get(1, 1, 1e6, d, 0) << nl;
		}
	}
}
                
signed main() {                   
	ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
   	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
        //cout << "Case " << i << ": ";
        solve();
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 8 ms 9164 KB Output is correct
4 Correct 6 ms 9256 KB Output is correct
5 Correct 7 ms 9292 KB Output is correct
6 Correct 6 ms 9420 KB Output is correct
7 Correct 2 ms 332 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 6 ms 9676 KB Output is correct
3 Correct 8 ms 9164 KB Output is correct
4 Correct 6 ms 9256 KB Output is correct
5 Correct 7 ms 9292 KB Output is correct
6 Correct 6 ms 9420 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 33 ms 1556 KB Output is correct
9 Correct 97 ms 19448 KB Output is correct
10 Correct 94 ms 19468 KB Output is correct
11 Correct 28 ms 1984 KB Output is correct
12 Correct 62 ms 3664 KB Output is correct
13 Correct 41 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 6 ms 9676 KB Output is correct
3 Correct 8 ms 9164 KB Output is correct
4 Correct 6 ms 9256 KB Output is correct
5 Correct 7 ms 9292 KB Output is correct
6 Correct 6 ms 9420 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 33 ms 1556 KB Output is correct
9 Correct 97 ms 19448 KB Output is correct
10 Correct 94 ms 19468 KB Output is correct
11 Correct 28 ms 1984 KB Output is correct
12 Correct 62 ms 3664 KB Output is correct
13 Correct 41 ms 3164 KB Output is correct
14 Correct 174 ms 19168 KB Output is correct
15 Correct 171 ms 19152 KB Output is correct
16 Correct 199 ms 19076 KB Output is correct
17 Correct 165 ms 19148 KB Output is correct
18 Correct 169 ms 19152 KB Output is correct