oj.uz

Submission #171091

# Submission time Handle Problem Language Result Execution time Memory
171091 2019-12-27T11:01:27 Z Lightning Simple game (IZhO17_game) C++14
100 / 100
 469 ms 19524 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll

const int szT = (1 << 20) - 1;

int n, m, h[szT], t[szT * 3], add[szT * 3];

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

void upd(int v, int tl, int tr, int l, int r, int x) {
	push(v, tl, tr);
	if(tr < l || r < tl) return;
	if(l <= tl && tr <= r) {
		add[v] += x;
		push(v, tl, tr);
		return;
	}
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, x);
	upd(v * 2 + 1, tm + 1, tr, l, r, x);
	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 () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> h[i];
	}
	for(int i = 1; i < n; ++i) {
		//if(1 < i) upd(1, 1, 1000000, min(h[i - 1], h[i]), max(h[i - 1], h[i]), 1);
		upd(1, 1, 1000000, min(h[i + 1], h[i]), max(h[i + 1], h[i]), 1);
	}
	/*for(int i = 1; i <= 10; ++i) {
		cout <<  get(1, 1, 1000000, i) <<' ';
	}
	cout << '\n';*/
	for(int i = 1; i <= m; ++i) {
		int type;
		cin >> type;
		if(type == 1) {
			int pos, val;
			cin >> pos >> val;
			if(1 < pos) upd(1, 1, 1000000, min(h[pos - 1], h[pos]), max(h[pos - 1], h[pos]), -1);
			if(pos < n) upd(1, 1, 1000000, min(h[pos + 1], h[pos]), max(h[pos + 1], h[pos]), -1);
			h[pos] = val;
			if(1 < pos) upd(1, 1, 1000000, min(h[pos - 1], h[pos]), max(h[pos - 1], h[pos]), 1);
			if(pos < n) upd(1, 1, 1000000, min(h[pos + 1], h[pos]), max(h[pos + 1], h[pos]), 1);
		} else {
			int qh;
			cin >> qh;
			cout << get(1, 1, 1000000, qh) <<'\n';
		}
	}
	return 0;
}
/*
3 3
1 5 1
2 3
1 1 5
2 3
*/
/*
	If you only do what you can do, 
	You will never be more than you are now!
------------------------------------------------------------------------------------------	
	We must all suffer from one of two pains: the pain of discipline or the pain of regret. 
	The difference is discipline weighs grams while regret weighs tons.
*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 18 ms 15096 KB Output is correct
3 Correct 18 ms 14712 KB Output is correct
4 Correct 17 ms 14840 KB Output is correct
5 Correct 18 ms 15096 KB Output is correct
6 Correct 18 ms 14948 KB Output is correct
7 Correct 15 ms 12792 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 18 ms 15096 KB Output is correct
3 Correct 18 ms 14712 KB Output is correct
4 Correct 17 ms 14840 KB Output is correct
5 Correct 18 ms 15096 KB Output is correct
6 Correct 18 ms 14948 KB Output is correct
7 Correct 15 ms 12792 KB Output is correct
8 Correct 81 ms 1912 KB Output is correct
9 Correct 209 ms 19448 KB Output is correct
10 Correct 212 ms 19448 KB Output is correct
11 Correct 72 ms 1656 KB Output is correct
12 Correct 127 ms 3576 KB Output is correct
13 Correct 94 ms 19320 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 18 ms 15096 KB Output is correct
3 Correct 18 ms 14712 KB Output is correct
4 Correct 17 ms 14840 KB Output is correct
5 Correct 18 ms 15096 KB Output is correct
6 Correct 18 ms 14948 KB Output is correct
7 Correct 15 ms 12792 KB Output is correct
8 Correct 81 ms 1912 KB Output is correct
9 Correct 209 ms 19448 KB Output is correct
10 Correct 212 ms 19448 KB Output is correct
11 Correct 72 ms 1656 KB Output is correct
12 Correct 127 ms 3576 KB Output is correct
13 Correct 94 ms 19320 KB Output is correct
14 Correct 434 ms 19524 KB Output is correct
15 Correct 442 ms 19448 KB Output is correct
16 Correct 443 ms 19480 KB Output is correct
17 Correct 462 ms 19504 KB Output is correct
18 Correct 469 ms 19448 KB Output is correct