Submission #794246

#	Time	Username	Problem	Language	Result	Execution time	Memory
794246		sumit_kk10	Simple game (IZhO17_game)	C++17	100 / 100	369 ms	15852 KiB

game

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define int long long
#define F first
#define S second
#define pb push_back
using namespace std;
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int> > , rb_tree_tag,tree_order_statistics_node_update>
const int N = 1e6 + 5, MOD = 1e9 + 7;
int n, q, a[N];

void solve(){
	cin >> n >> q;
	for(int i = 1; i <= n; ++i)
		cin >> a[i];
	ordered_set mx, mn;
	for(int i = 2; i <= n; ++i)
		mx.insert({max(a[i], a[i - 1]), i});
	for(int i = 2; i <= n; ++i)
		mn.insert({min(a[i], a[i - 1]), i});
	while(q--){
		int t;
		cin >> t;
		if(t == 1){
			int i, x;
			cin >> i >> x;
			if(i + 1 <= n){
				auto p = mx.find({max(a[i], a[i + 1]), i + 1});
				mx.erase(p);
				p = mn.find({min(a[i], a[i + 1]), i + 1});
				mn.erase(p);
			}
			if(i - 1 >= 1){
				auto p = mx.find({max(a[i], a[i - 1]), i});
				mx.erase(p);
				p = mn.find({min(a[i], a[i - 1]), i});
				mn.erase(p);
			}
			a[i] = x;
			if(i + 1 <= n){
				mx.insert({max(a[i], a[i + 1]), i + 1});
				mn.insert({min(a[i], a[i + 1]), i + 1});
			}
			if(i - 1 >= 1){
				mx.insert({max(a[i], a[i - 1]), i});
				mn.insert({min(a[i], a[i - 1]), i});
			}
		}
		else{
			int k;
			cin >> k;
			int ans = mx.size() - mx.order_of_key({k, 0});
			ans -= mn.size() - mn.order_of_key({k, 0});
			cout << ans << "\n";
		}
	}
}

int32_t main(){
	fast;
	int t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51