oj.uz

Submission #930613

# Submission time Handle Problem Language Result Execution time Memory
930613 2024-02-20T07:58:14 Z allin27x Simple game (IZhO17_game) C++17
100 / 100
 250 ms 23176 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 2e5+7;

int t[2*MAXN];
int ina[MAXN];
int maxv;

map<int,int> key;


void update(int l, int r, int v){
	for (l+=maxv, r+=maxv+1; l<r; l>>=1, r>>=1){
		if (l&1) t[l++] += v;
		if (r&1) t[--r] += v;
	}
}

int ans(int ind){
	int res = 0;
	for (int i=ind+maxv; i>0; i>>=1) res+=t[i];
	return res;
}



signed main(){
	int n,m; cin>>n>>m;
	vector<int> values;
	vector<tuple<int,int,int>> queries(m);
	for (int i=0; i<n; i++) cin>>ina[i];
	for (int i=0; i<n; i++) values.push_back(ina[i]);
	for (int i=0; i<m; i++){
		int r; cin>>r;
		if (r==1){
			int a,b; cin>>a>>b; a--; values.push_back(b); queries[i] = {1,a,b};
		} else {
			int k; cin>>k; values.push_back(k); queries[i] = {2,k,0};
		}
	}
	sort(values.begin(), values.end());
	int ind = 0;
	for (int i=0; i<values.size(); i++){
		if (key.count(values[i])) continue;
		key[values[i]]  = ind++;
	}
	for (int i=0; i<n; i++) ina[i] = key[ina[i]];
	for (int i=0; i<m; i++){
		int r = get<0> (queries[i]); 
		if (r==1){
			get<2> (queries[i]) = key[get<2> (queries[i])];
		} else {
			get<1> (queries[i]) = key[get<1> (queries[i])];
		}
	}
	maxv = ind;
	// for (int i=0; i<n; i++) cout<<ina[i]<<' '; cout<<'\n';
	// for (auto [a,b,c]: queries){
	// 	if (a==1) {
	// 		cout<<b<<' '<<c<<'\n';
	// 	} else {
	// 		cout<<b<<'\n';
	// 	}
	// }

	for (int i=0; i<n-1; i++){
		update(min(ina[i], ina[i+1]), max(ina[i],ina[i+1]), 1);
	}
	for (auto [a,b,c]: queries){
		if (a==1){
			if (b){
				update(min(ina[b], ina[b-1]), max(ina[b], ina[b-1]), -1);
				update(min(ina[b-1], c), max(ina[b-1], c), 1);
			}
			if (b!=n-1){
				update(min(ina[b], ina[b+1]), max(ina[b], ina[b+1]), -1);
				update(min(ina[b+1], c), max(ina[b+1], c), 1);
			}
			ina[b] = c;
		} else {
			cout<<ans(b)<<'\n';
		}
	}
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:45:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i=0; i<values.size(); i++){
      |                ~^~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2560 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2560 KB Output is correct
8 Correct 54 ms 7680 KB Output is correct
9 Correct 219 ms 23176 KB Output is correct
10 Correct 195 ms 22980 KB Output is correct
11 Correct 45 ms 7620 KB Output is correct
12 Correct 129 ms 10436 KB Output is correct
13 Correct 148 ms 14484 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 2 ms 2560 KB Output is correct
8 Correct 54 ms 7680 KB Output is correct
9 Correct 219 ms 23176 KB Output is correct
10 Correct 195 ms 22980 KB Output is correct
11 Correct 45 ms 7620 KB Output is correct
12 Correct 129 ms 10436 KB Output is correct
13 Correct 148 ms 14484 KB Output is correct
14 Correct 229 ms 22464 KB Output is correct
15 Correct 250 ms 22464 KB Output is correct
16 Correct 227 ms 22612 KB Output is correct
17 Correct 222 ms 22436 KB Output is correct
18 Correct 229 ms 22872 KB Output is correct