oj.uz

Submission #572880

# Submission time Handle Problem Language Result Execution time Memory
572880 2022-06-05T12:26:15 Z vovamr Simple game (IZhO17_game) C++17
100 / 100
 68 ms 6840 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 1e6 + 100; int f[N];
inline void upd(int i, int x) { i += 3; for (; i < N; i += i & -i) f[i] += x; }
inline int get(int i) { i += 3; int ans = 0; for (; i; i -= i & -i) { ans += f[i]; } return ans; }

inline void solve() {
	int n, q;
	cin >> n >> q;
	ve<int> a(n);
	for (auto &i : a) cin >> i;

	auto add = [&](int i) {
		int l = min(a[i - 1], a[i]);
		int r = max(a[i - 1], a[i]);
		upd(l, +1), upd(r + 1, -1);
	};
	auto del = [&](int i) {
		int l = min(a[i - 1], a[i]);
		int r = max(a[i - 1], a[i]);
		upd(l, -1), upd(r + 1, +1);
	};

	for (int i = 1; i < n; ++i) add(i);

	while (q--) {
		int e;
		cin >> e;
		if (e == 1) {
			int i, x;
			cin >> i >> x, --i;
			if (i) del(i);
			if (i + 1 < n) del(i + 1);
			a[i] = x;
			if (i) add(i);
			if (i + 1 < n) add(i + 1);
		}
		else {
			int x;
			cin >> x;
			cout << get(x) << '\n';
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 4056 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 3 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 2 ms 4056 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 4056 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 3 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 2 ms 4056 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 42 ms 1724 KB Output is correct
9 Correct 41 ms 6832 KB Output is correct
10 Correct 52 ms 6740 KB Output is correct
11 Correct 31 ms 1600 KB Output is correct
12 Correct 35 ms 2760 KB Output is correct
13 Correct 43 ms 2812 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 4056 KB Output is correct
3 Correct 2 ms 4052 KB Output is correct
4 Correct 3 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 2 ms 4056 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 42 ms 1724 KB Output is correct
9 Correct 41 ms 6832 KB Output is correct
10 Correct 52 ms 6740 KB Output is correct
11 Correct 31 ms 1600 KB Output is correct
12 Correct 35 ms 2760 KB Output is correct
13 Correct 43 ms 2812 KB Output is correct
14 Correct 68 ms 6824 KB Output is correct
15 Correct 64 ms 6840 KB Output is correct
16 Correct 51 ms 6732 KB Output is correct
17 Correct 53 ms 6792 KB Output is correct
18 Correct 67 ms 6760 KB Output is correct