Submission #386352

#	Time	Username	Problem	Language	Result	Execution time	Memory
386352		vanic	Simple game (IZhO17_game)	C++14	100 / 100	78 ms	6924 KiB

game

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <array>
#include <bitset>

using namespace std;

const int maxn=1e5+5, maxh=1e6+5;

struct logaritamska{
	int l[maxh];
	void update(int x, int val){
		for(; x<maxh; x+=(x & -x)){
			l[x]+=val;
		}
	}
	int query(int x){
		int sol=0;
		for(; x>0; x-=(x & -x)){
			sol+=l[x];
		}
		return sol;
	}
};

int h[maxn];
logaritamska L;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i=0; i<n; i++){
		cin >> h[i];
		if(i){
			L.update(min(h[i], h[i-1]), 1);
			L.update(max(h[i], h[i-1]), -1);
		}
	}
	int a, b, c;
	for(int i=0; i<m; i++){
		cin >> a;
		if(a==1){
			cin >> b >> c;
			b--;
			if(b){
				L.update(min(h[b], h[b-1]), -1);
				L.update(max(h[b], h[b-1]), 1);
				L.update(min(c, h[b-1]), 1);
				L.update(max(c, h[b-1]), -1);
			}
			if(b<n-1){
				L.update(min(h[b], h[b+1]), -1);
				L.update(max(h[b], h[b+1]), 1);
				L.update(min(c, h[b+1]), 1);
				L.update(max(c, h[b+1]), -1);
			}
			h[b]=c;
		}
		else{
			cin >> b;
			cout << L.query(b) << '\n';
		}
	}
	return 0;
}

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