Submission #526115

#	Time	Username	Problem	Language	Result	Execution time	Memory
526115		ezdp	Simple game (IZhO17_game)	C++14	100 / 100	241 ms	5624 KiB

game

#pragma GCC target ("sse4")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

#define endl '\n'
#define pb push_back
#define fr first
#define sc second
#define ll long long int
#define ld long double
#define lsb(idx) idx&(-idx)
#define bin(x) bitset<32>(x).to_string()
#define all(A) A.begin(), A.end()
#define de(x) cout << #x << " = " << x << endl;

using namespace std;
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using matrix = vector<vector<T>>;
/// find_by_order(x) -> x-th element in the set
/// order_of_key(x)  -> how many elements are less than x
/// insert(x)		 -> inserts x into the set

const int MAXN = 1e6 + 6;

int BIT[MAXN];

void add(int x, int v){
	for(++ x; x < MAXN; x += lsb(x))
		BIT[x] += v;
}

int qry(int x){
	int ret = 0;
	for(++ x; x > 0; x -= lsb(x))
		ret += BIT[x];
	return ret;
}

int main(){
	/// ios_base::sync_with_stdio(false); cin.tie(NULL);
	/// freopen("filename.in" , "r", stdin); 
	/// freopen("filename.out", "w", stdout);
	int n, q; cin >> n >> q;
	vector<int> A(n);
	for(auto &x : A) cin >> x;
	for(int i = 0; i < n - 1; i ++){
		add(min(A[i], A[i + 1]), +1);
		add(max(A[i], A[i + 1]), -1);
	}
	for(int i = 0; i < q; i ++){
		int t; cin >> t;
		if(t == 1){
			int i, y; cin >> i >> y; -- i;
			if(i != n - 1){
				add(min(A[i], A[i + 1]), -1);
				add(max(A[i], A[i + 1]), +1);
			}
			if(i != 0){
				add(min(A[i], A[i - 1]), -1);
				add(max(A[i], A[i - 1]), +1);
			}
			A[i] = y;
			if(i != n - 1){
				add(min(A[i], A[i + 1]), +1);
				add(max(A[i], A[i + 1]), -1);
			}
			if(i != 0){
				add(min(A[i], A[i - 1]), +1);
				add(max(A[i], A[i - 1]), -1);
			}
		}
		if(t == 2){
			int y; cin >> y;
			cout << qry(y) << endl;
		}
	}
}
/**

*/

Compilation message (stderr)

game.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
game.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

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