oj.uz

Submission #88167

# Submission time Handle Problem Language Result Execution time Memory
88167 2018-12-04T07:44:52 Z dimash241 Simple game (IZhO17_game) C++14
100 / 100
 118 ms 26688 KB 
# 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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 7296 KB Output is correct
3 Correct 9 ms 7296 KB Output is correct
4 Correct 9 ms 7380 KB Output is correct
5 Correct 8 ms 7500 KB Output is correct
6 Correct 8 ms 7704 KB Output is correct
7 Correct 4 ms 7704 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 7296 KB Output is correct
3 Correct 9 ms 7296 KB Output is correct
4 Correct 9 ms 7380 KB Output is correct
5 Correct 8 ms 7500 KB Output is correct
6 Correct 8 ms 7704 KB Output is correct
7 Correct 4 ms 7704 KB Output is correct
8 Correct 49 ms 7704 KB Output is correct
9 Correct 90 ms 12148 KB Output is correct
10 Correct 88 ms 13788 KB Output is correct
11 Correct 48 ms 13788 KB Output is correct
12 Correct 50 ms 13788 KB Output is correct
13 Correct 55 ms 13788 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 7296 KB Output is correct
3 Correct 9 ms 7296 KB Output is correct
4 Correct 9 ms 7380 KB Output is correct
5 Correct 8 ms 7500 KB Output is correct
6 Correct 8 ms 7704 KB Output is correct
7 Correct 4 ms 7704 KB Output is correct
8 Correct 49 ms 7704 KB Output is correct
9 Correct 90 ms 12148 KB Output is correct
10 Correct 88 ms 13788 KB Output is correct
11 Correct 48 ms 13788 KB Output is correct
12 Correct 50 ms 13788 KB Output is correct
13 Correct 55 ms 13788 KB Output is correct
14 Correct 104 ms 19016 KB Output is correct
15 Correct 118 ms 20800 KB Output is correct
16 Correct 107 ms 22808 KB Output is correct
17 Correct 107 ms 24672 KB Output is correct
18 Correct 113 ms 26688 KB Output is correct