Submission #88167

#	Time	Username	Problem	Language	Result	Execution time	Memory
88167		dimash241	Simple game (IZhO17_game)	C++14	100 / 100	118 ms	26688 KiB

game

# include <stdio.h>
# include <bits/stdc++.h>


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (int i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (int i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace std;

inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
int f[mxn];
int cnt[mxn];
int a[N];

void upd (int pos, int x) {
	for (int i = pos; i < mxn; i |= (i + 1))
		f[i] += x;
}

int get (int r) {
	int res = 0;
	while (r > 0) {
		res += f[r];
		r = (r & (r + 1)) - 1;
	}

	return res;
}

int main () {
	SpeedForce;               
    cin >> n >> m;
    For (i, 1, n) {
    	cin >> a[i];
    	if (i > 1) upd (min(a[i - 1], a[i]), 1), upd(max(a[i - 1], a[i]), -1);
    	cnt[a[i]] ++;
    }

    For (i, 1, m) {
    	int t, x, y;
    	cin >> t >> x;
    	if (t == 2) {
    		cout << get(x) + cnt[x] << '\n';
    	} else {
    		cin >> y;
    		cnt[a[x]] --;
    		if (x > 1) upd (min(a[x - 1], a[x]), -1), upd(max(a[x - 1], a[x]), 1);
    		if (x < n) upd (min(a[x + 1], a[x]), -1), upd(max(a[x + 1], a[x]), 1);
    		a[x] = y;
    		if (x > 1) upd (min(a[x - 1], a[x]), 1), upd(max(a[x - 1], a[x]), -1);
    		if (x < n) upd (min(a[x + 1], a[x]), 1), upd(max(a[x + 1], a[x]), -1);
    		
    		cnt[a[x]] ++;
    	}
    }
    return Accepted;
}

// Coded By OB

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