Submission #1134477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134477		Agageldi	Simple game (IZhO17_game)	C++17	0 / 100	0 ms	320 KiB

game

/*
ID: agageld1
LANG: C++17
TASK:
siuu
*/
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 20000005
#define pb push_back
#define ff first
#define ss second
#define sz(s) (int)s.size()

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, t, a[N], p[N], ans ,m;
//void upd(int l,int r,int ind,int x,int y,int bal) {
//	if(l > y || r < x) return;
//	if(l >= x && r <= y) {
//		p[ind] += bal;
//		return;
//	}
//	int mid = (l+r)/2;
//	upd(l,mid,x,y,bal);
//	upd(mid+1,r,x,y,bal);
//	p[ind] = p[ind * 2] + p[ind * 2 + 1];
//}
void solve(int l,int r,int ind,int x) {
	if(l > x || r < x) return;
	if(l <= x && r >= x) {
		ans += p[ind];
		return;
	}
	int mid =(l+r)/2;
	solve(l,mid,ind*2,x);
	solve(mid+1,r,ind*2+1,x);
}
void build(int l,int r,int ind,int x,int y) {
	if(l > y || r < x) return;
	if(l >= x && r <= y) {
		p[ind]++;
		return;
	}
	int mid = (l+r)/2;
	build(l,mid,ind*2,x,y);
	build(mid+1,r,ind*2+1,x,y);
	p[ind] = p[ind*2] + p[ind*2 + 1];
}

int main (){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		if(i > 1) {
			build(1, 1e6, 1, a[i] , a[i - 1]);
		}
	}
	for(int i=1;i <= m; i++) {
		int x, y;
		cin >> t;
		if(t == 1) {
//			cin >> x >> y;
//			if(x != n)upd(1,n,1,min(a[x],a[x+1]), max(a[x],a[x + 1]), -1);
//			if(x != 1)upd(1,n,1,min(a[x],a[x-1]), max(a[x],a[x- 1]), -1);
//			a[x] = y;
//			if(x != n)upd(1,n,1,min(a[x],a[x+1]), max(a[x],a[x + 1]), 1);
//			if(x != 1)upd(1,n,1,min(a[x],a[x-1]), max(a[x],a[x- 1]), 1);
//			continue;
		}
		cin >> x;
		ans = 0;
		solve(1,1e6,1,x);
		cout << ans << '\n';
	}
}

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