oj.uz

Submission #522913

# Submission time Handle Problem Language Result Execution time Memory
522913 2022-02-06T12:40:48 Z dostigator Simple game (IZhO17_game) C++14
100 / 100
 176 ms 11240 KB 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
#define IShowSpeed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define popcnt __builtin_popcount
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mii map<int,int>
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define pb push_back
#define vt vector
#define endl '\n'
#define X first
#define Y second
typedef long double ld;
typedef long long ll;
const ll dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},N=1e6+10;
const ll mod=1e9+7,inf=1e18;
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) << endl;
		}
	}
}
int main() {
    IShowSpeed;
    int tt=1;
    //cin>>tt;
    while(tt--) solve();
}

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 6580 KB Output is correct
3 Correct 6 ms 6348 KB Output is correct
4 Correct 5 ms 6476 KB Output is correct
5 Correct 5 ms 6476 KB Output is correct
6 Correct 4 ms 6624 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 0 ms 332 KB Output is correct
2 Correct 7 ms 6580 KB Output is correct
3 Correct 6 ms 6348 KB Output is correct
4 Correct 5 ms 6476 KB Output is correct
5 Correct 5 ms 6476 KB Output is correct
6 Correct 4 ms 6624 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 33 ms 1652 KB Output is correct
9 Correct 90 ms 11076 KB Output is correct
10 Correct 101 ms 11232 KB Output is correct
11 Correct 29 ms 1608 KB Output is correct
12 Correct 59 ms 2952 KB Output is correct
13 Correct 38 ms 2728 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 6580 KB Output is correct
3 Correct 6 ms 6348 KB Output is correct
4 Correct 5 ms 6476 KB Output is correct
5 Correct 5 ms 6476 KB Output is correct
6 Correct 4 ms 6624 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 33 ms 1652 KB Output is correct
9 Correct 90 ms 11076 KB Output is correct
10 Correct 101 ms 11232 KB Output is correct
11 Correct 29 ms 1608 KB Output is correct
12 Correct 59 ms 2952 KB Output is correct
13 Correct 38 ms 2728 KB Output is correct
14 Correct 169 ms 11240 KB Output is correct
15 Correct 176 ms 11012 KB Output is correct
16 Correct 163 ms 11100 KB Output is correct
17 Correct 165 ms 11012 KB Output is correct
18 Correct 168 ms 11084 KB Output is correct