Submission #930613

#	Time	Username	Problem	Language	Result	Execution time	Memory
930613		allin27x	Simple game (IZhO17_game)	C++17	100 / 100	250 ms	23176 KiB

game

#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 (stderr)

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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51