Submission #37229

#	Time	Username	Problem	Language	Result	Execution time	Memory
37229		temurbek_khujaev	Simple game (IZhO17_game)	C++14	0 / 100	0 ms	54260 KiB

game

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <math.h>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <string.h>
#include <cstring>
#include <queue>
#include <iomanip>
#include <istream>
#include <map>
#include <list>
#include <stack>
#include <numeric>
#include <ostream>
#include <set>
#include <cassert>
#include <sstream>
#include <string>
#include <utility>
#include <stdio.h>
#include <vector>
using namespace std;
#define dout if (debug) cout
#define PB push_back
#define MP make_pair
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int((x.size())))
typedef long double ld;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<PII> VPI;
#define REP(i,a,n) for (int i=a;i<n;i++)
#define db(x) cerr << #x << " = " << x << endl
#define PER(i,a,n) for (int i=n-1;i>=a;i--)
const int INF = 1000000404;
const ll MOD = 1000000007ll;
const ld PI = acos(-1.0);
const ld EPS = 1e-9;
template <typename t1, typename t2> inline void upmax(t1 &a, t2 b) { a = max(a, (t1)b); }
template <typename t1, typename t2> inline void upmin(t1 &a, t2 b) { a = min(a, (t1)b); }
template <typename T>inline T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }
template <typename T>inline T lcm(T a, T b) { return a*(b / gcd(a, b)); }
template <typename T>inline T sqr(T a) { return a*a; }
template <typename T>inline bool pal(T &x)
{
	int n = SZ(x); REP(i, 0, n / 2) { if (x[i] != x[n - i - 1]) return 0; }return 1;
}
template <typename T>inline void rev(T &x) { int n = SZ(x); REP(i, 0, n / 2) swap(x[i], x[n - i - 1]); }
int month[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int dy[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
inline ll mp(ll a, ll b) { return (a << 31) + b; }
class compare{
public:
	bool operator()(const int a, const int b) const {
		return 1;
	}
};
int SQ = 400;

#define debug 1
#define N 1111111
int t[N * 4];
int p[N * 4];
int h[N * 4];
void update(int l, int r, int delta, int v = 1, int tl = 1, int tr = 1e6) {
	if (l > tr || r < tl) return;
	if (l <= tl&&tr <= r) {
		t[v] += delta;
		return;
	}
	int tm = (tl + tr) >> 1;
	update(l, r, delta, v + v, tl, tm);
	update(l, r, delta, v + v + 1, tm + 1, tr);
}
int get(int pos, int v = 1, int tl = 1, int tr = 1e6) {
	if (tl == tr) return t[v];
	int tm = (tl + tr) >> 1;
	if (pos <= tm) return t[v] + get(pos, v + v, tl, tm);
	else return t[v] + get(pos, v + v + 1, tm + 1, tr);
}

void solve()
{
	int n, m;
	cin >> n >> m;
	REP(i, 1, n + 1) cin >> h[i];
	REP(i, 2, n) {
		int a = h[i - 1];
		int b = h[i];
		int c = h[i + 1];
		update(min(a, b), max(a, b), 1);
		update(min(c, b), max(c, b), 1);
	}
	REP(i, 0, m) {
		int type, pos, val, H;
		cin >> type;
		if (type == 1) {
			cin >> pos >> val;
			int a = h[pos - 1];
			int b = h[pos];
			int c = h[pos + 1];
			if (pos != 1) {
				update(min(a, b), max(a, b), -1);
				update(min(a, val), max(a, val), 1);
			}
			if (pos != n) {
				update(min(c, b), max(c, b), -1);
				update(min(c, val), max(c, val), 1);
			}
			h[pos] = val;
		}
		else {
			cin >> H;
			cout << get(H) << endl;
		}
	}

}

int main()
{
	ios_base::sync_with_stdio(false);	cin.tie(0);	cout.tie(0);
	int t = 1;
	//cin>>t;

	while (t--) {
		solve();
	};


	//getchar();
//	getchar();
	return 0;
}

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