oj.uz

Submission #386210

# Submission time Handle Problem Language Result Execution time Memory
386210 2021-04-06T05:33:20 Z Kalashnikov Simple game (IZhO17_game) C++17
100 / 100
 101 ms 11248 KB 
#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 #define int ll
const int N = 1e6+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7 , P = 6547;

int a[N] , f[N];

void upd(int pos , int val) {
	for(; pos < N; pos |= pos+1) {
		f[pos] += val;
	}
}

int get(int x) {
	int res = 0;
	for(; x > 0; x &= x+1 , x--) {
		res += f[x];
	}
	return res;
}

void solve() {
	int n , m;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		if(i != 1) {
			upd(min(a[i] , a[i-1]) , 1);
			upd(max(a[i] , a[i-1]) , -1);
		}
	}
	while(m --) {
		int t;
		cin >> t;
		if(t == 1) {
			int i , val;
			cin >> i >> val;
			if(i != 1) {
				upd(min(a[i] , a[i-1]) , -1);
				upd(max(a[i] , a[i-1]) , 1);
			}
			if(i != n) {
				upd(min(a[i] , a[i+1]) , -1);
				upd(max(a[i] , a[i+1]) , 1);
			}
			a[i] = val;
			if(i != 1) {
				upd(min(a[i] , a[i-1]) , 1);
				upd(max(a[i] , a[i-1]) , -1);
			}
			if(i != n) {
				upd(min(a[i] , a[i+1]) , 1);
				upd(max(a[i] , a[i+1]) , -1);
			}
		}
		else {
			int x;
			cin >> x;
			cout << get(x) << '\n';
		}
	}
	
}
/*
*/
main() {
    ios;
    int tt = 1;
    //cin >> tt;
    while(tt --) {
        solve();
    }
    return 0;
}

Compilation message

game.cpp:75:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main() {
      |      ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 5 ms 6892 KB Output is correct
3 Correct 6 ms 6636 KB Output is correct
4 Correct 5 ms 6764 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6892 KB Output is correct
7 Correct 2 ms 492 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 5 ms 6892 KB Output is correct
3 Correct 6 ms 6636 KB Output is correct
4 Correct 5 ms 6764 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6892 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 43 ms 2156 KB Output is correct
9 Correct 68 ms 11244 KB Output is correct
10 Correct 67 ms 11244 KB Output is correct
11 Correct 42 ms 2028 KB Output is correct
12 Correct 45 ms 3436 KB Output is correct
13 Correct 45 ms 3308 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 5 ms 6892 KB Output is correct
3 Correct 6 ms 6636 KB Output is correct
4 Correct 5 ms 6764 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6892 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 43 ms 2156 KB Output is correct
9 Correct 68 ms 11244 KB Output is correct
10 Correct 67 ms 11244 KB Output is correct
11 Correct 42 ms 2028 KB Output is correct
12 Correct 45 ms 3436 KB Output is correct
13 Correct 45 ms 3308 KB Output is correct
14 Correct 91 ms 11244 KB Output is correct
15 Correct 95 ms 11248 KB Output is correct
16 Correct 101 ms 11152 KB Output is correct
17 Correct 94 ms 11244 KB Output is correct
18 Correct 93 ms 11244 KB Output is correct