Submission #927792

#	Time	Username	Problem	Language	Result	Execution time	Memory
927792		penguin133	Simple game (IZhO17_game)	C++17	100 / 100	88 ms	8904 KiB

game

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int ft[300005];
const int lim = 3e5;
void upd(int l, int r, int v){
	if(l > r)swap(l, r);
	for(; l <= lim; l += (l & -l))ft[l] += v;
	r++;
	for(; r <= lim; r += ( r & -r))ft[r] -= v;
}

int qry(int p){
	int res = 0;
	for(;p;p-= (p & -p))res += ft[p];
	return res;
}

int Q[3][100005], A[100005];

void solve(){
	int n, q; cin >> n >> q;
	vector <int> sad;
	for(int i = 1; i <= n; i++)cin >> A[i], sad.push_back(A[i]);
	for(int i = 1; i <= q; i++){
		cin >> Q[0][i];
		if(Q[0][i] == 1)cin >> Q[1][i] >> Q[2][i], sad.push_back(Q[2][i]);
		else cin >> Q[1][i], sad.push_back(Q[1][i]);
	}
	sort(sad.begin(), sad.end());
	sad.erase(unique(sad.begin(), sad.end()), sad.end());
	for(int i = 1; i <= n; i++){
		A[i] = lower_bound(sad.begin(), sad.end(), A[i]) - sad.begin() + 1;
	}
	for(int i = 1; i < n; i++)upd(A[i], A[i + 1], 1);
	for(int i = 1; i <= q; i++){
		if(Q[0][i] == 1){
			if(Q[1][i] != 1)upd(A[Q[1][i]], A[Q[1][i] - 1], -1);
			if(Q[1][i] != n)upd(A[Q[1][i]], A[Q[1][i] + 1], -1);
			A[Q[1][i]] = lower_bound(sad.begin(), sad.end(), Q[2][i]) - sad.begin() + 1;
			int x = Q[1][i];
			if(x != 1)upd(A[x], A[x - 1], 1);
			if(x != n)upd(A[x], A[x + 1] ,1);
		}
		else{
			int tmp = lower_bound(sad.begin(), sad.end(), Q[1][i]) - sad.begin() + 1;
			cout << qry(tmp) << '\n';
		}
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

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

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