oj.uz

Submission #505575

# Submission time Handle Problem Language Result Execution time Memory
505575 2022-01-11T05:50:13 Z shmad Simple game (IZhO17_game) C++17
100 / 100
 185 ms 19780 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC target ("avx2")

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvi = vt< vt<int> >;

const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60);
const double eps = 1e-6;

int n, m, t[N * 4], h[N];

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

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

void solve () {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> h[i];
	for (int i = 2; i <= n; i++) {
		int l = h[i - 1], r = h[i];
		if (l > r) swap(l, r);
		upd(l, r, +1);
	}
	for (int i = 1; i <= m; i++) {
		int tp;
		cin >> tp;
		if (tp == 1) {
			int pos, val;
			cin >> pos >> val;
			if (pos - 1 >= 1) {
				int l = h[pos - 1], r = h[pos];
				if (l > r) swap(l, r);
				upd(l, r, -1);
			}
			if (pos + 1 <= n) {
				pos++;
				int l = h[pos - 1], r = h[pos];
				if (l > r) swap(l, r);
				upd(l, r, -1);
				pos--;
			}
			h[pos] = val;
			if (pos - 1 >= 1) {
				int l = h[pos - 1], r = h[pos];
				if (l > r) swap(l, r);
				upd(l, r, +1);
			}
			if (pos + 1 <= n) {
				pos++;
				int l = h[pos - 1], r = h[pos];
				if (l > r) swap(l, r);
				upd(l, r, +1);
				pos--;
			}
		}
		if (tp == 2) {
			int H;
			cin >> H;
			cout << get(H) << '\n';
		}
	}
	cout << '\n';
}

bool testcases = 0;
                  
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int test = 1;
    if (testcases) cin >> test;
    for (int cs = 1; cs <= test; cs++) {
        solve();
    }
}

Compilation message

game.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
game.cpp:34:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
game.cpp: In function 'long long int get(long long int, long long int, long long int, long long int)':
game.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |  int tm = tl + tr >> 1, res;
      |           ~~~^~~~
game.cpp:43:25: warning: unused variable 'res' [-Wunused-variable]
   43 |  int tm = tl + tr >> 1, res;
      |                         ^~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 5 ms 9468 KB Output is correct
3 Correct 7 ms 9284 KB Output is correct
4 Correct 7 ms 9420 KB Output is correct
5 Correct 7 ms 9420 KB Output is correct
6 Correct 8 ms 9600 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 5 ms 9468 KB Output is correct
3 Correct 7 ms 9284 KB Output is correct
4 Correct 7 ms 9420 KB Output is correct
5 Correct 7 ms 9420 KB Output is correct
6 Correct 8 ms 9600 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 39 ms 2116 KB Output is correct
9 Correct 103 ms 19760 KB Output is correct
10 Correct 107 ms 19776 KB Output is correct
11 Correct 35 ms 1976 KB Output is correct
12 Correct 79 ms 3588 KB Output is correct
13 Correct 65 ms 3148 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 5 ms 9468 KB Output is correct
3 Correct 7 ms 9284 KB Output is correct
4 Correct 7 ms 9420 KB Output is correct
5 Correct 7 ms 9420 KB Output is correct
6 Correct 8 ms 9600 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 39 ms 2116 KB Output is correct
9 Correct 103 ms 19760 KB Output is correct
10 Correct 107 ms 19776 KB Output is correct
11 Correct 35 ms 1976 KB Output is correct
12 Correct 79 ms 3588 KB Output is correct
13 Correct 65 ms 3148 KB Output is correct
14 Correct 175 ms 19772 KB Output is correct
15 Correct 172 ms 19728 KB Output is correct
16 Correct 172 ms 19772 KB Output is correct
17 Correct 185 ms 19700 KB Output is correct
18 Correct 185 ms 19780 KB Output is correct