oj.uz

Submission #884563

# Submission time Handle Problem Language Result Execution time Memory
884563 2023-12-07T16:36:47 Z tsumondai Simple game (IZhO17_game) C++14
100 / 100
 243 ms 21308 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e9, mod = 1e9 + 7;
 
int n, m, k, a[N], q;

struct Node{
	int lazy;
	int val;
} nodes[N*4];

void down(int id) {
	int t=nodes[id].lazy;
	nodes[id*2].lazy+=t;
	nodes[id*2].val+=t;
	nodes[id*2+1].lazy+=t;
	nodes[id*2+1].val+=t;
	nodes[id].lazy=0;
}

void update(int id, int l, int r, int u, int v, int val) {
    if (v < l || r < u) {
        return;
    }
    if (u <= l && r <= v) {
        nodes[id].val += val;
        nodes[id].lazy += val;
        return;
    }
    int mid = (l + r) / 2;

    down(id); 

    update(id*2, l, mid, u, v, val);
    update(id*2+1, mid+1, r, u, v, val);

    nodes[id].val = (nodes[id*2].val+nodes[id*2+1].val);
}

int get(int id, int l, int r, int u, int v) {
	if (u>r || v<l /*|| l>r || u>v*/) return 0;
	if (l>=u && r<=v) return nodes[id].val;
	down(id);
	int mid=(l+r)/2;
	return (get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v));
}

void process() {
	cin >> n >> q;
	foru(i,1,n) cin >> a[i];
	foru(i,2,n) {
		int lo=min(a[i-1], a[i]);
		int hi=max(a[i-1], a[i]);
		update(1,1,N,lo,hi,1);
	}

	while (q--) {
		int type; cin >> type;
		if (type==1) {
			int pos, val; cin >> pos >> val;
			// update
			int lo, hi;
			if (pos==n) {
				lo=min(a[pos], a[pos-1]); 
				hi=max(a[pos-1], a[pos]);
				update(1,1,N,lo,hi,-1);
				a[pos]=val;
				lo=min(a[pos], a[pos-1]); 
				hi=max(a[pos-1], a[pos]);
				update(1,1,N,lo,hi,1);
				continue;
			}
			if (pos==1) {
				lo=min(a[pos], a[pos+1]); 
				hi=max(a[pos], a[pos+1]);
				update(1,1,N,lo,hi,-1);
				a[pos]=val;
				lo=min(a[pos], a[pos+1]); 
				hi=max(a[pos], a[pos+1]);
				update(1,1,N,lo,hi,1);
				continue;
			}
			// left
			int old=a[pos];
			lo=min(a[pos], a[pos-1]); 
			hi=max(a[pos], a[pos-1]);
			update(1,1,N,lo,hi,-1);
			a[pos]=val;
			lo=min(a[pos], a[pos-1]); 
			hi=max(a[pos], a[pos-1]);
			update(1,1,N,lo,hi,1);
			// right
			a[pos]=old;
			lo=min(a[pos], a[pos+1]); 
			hi=max(a[pos], a[pos+1]);
			update(1,1,N,lo,hi,-1);
			a[pos]=val;
			lo=min(a[pos], a[pos+1]); 
			hi=max(a[pos], a[pos+1]);
			update(1,1,N,lo,hi,1);
			continue;
		} else {
			int height; cin >> height;
			// query
			cout << get(1,1,N,height,height) << '\n';
		}
	}
    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    process();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}

// dont stop

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 6 ms 19124 KB Output is correct
5 Correct 5 ms 19036 KB Output is correct
6 Correct 5 ms 19128 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 6 ms 19124 KB Output is correct
5 Correct 5 ms 19036 KB Output is correct
6 Correct 5 ms 19128 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 53 ms 9596 KB Output is correct
9 Correct 132 ms 21240 KB Output is correct
10 Correct 120 ms 21244 KB Output is correct
11 Correct 55 ms 9484 KB Output is correct
12 Correct 81 ms 12520 KB Output is correct
13 Correct 83 ms 21056 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 6 ms 19124 KB Output is correct
5 Correct 5 ms 19036 KB Output is correct
6 Correct 5 ms 19128 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 53 ms 9596 KB Output is correct
9 Correct 132 ms 21240 KB Output is correct
10 Correct 120 ms 21244 KB Output is correct
11 Correct 55 ms 9484 KB Output is correct
12 Correct 81 ms 12520 KB Output is correct
13 Correct 83 ms 21056 KB Output is correct
14 Correct 227 ms 21076 KB Output is correct
15 Correct 243 ms 21308 KB Output is correct
16 Correct 207 ms 21244 KB Output is correct
17 Correct 228 ms 21248 KB Output is correct
18 Correct 221 ms 21236 KB Output is correct