Submission #91344

#	Time	Username	Problem	Language	Result	Execution time	Memory
91344		davitmarg	Simple game (IZhO17_game)	C++17	100 / 100	359 ms	16440 KiB

game

/*
DEATH-MATCH
Davit-Marg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <fstream>  
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;
int n, m,a[100005],t[4*1000006];

void update(int v,int l,int r,int p,int val)
{
	if (l == r)
	{
		t[v] += val;
		return;
	}
	int m = (l + r) / 2;
	if (p <= m)
		update(v * 2, l, m, p, val);
	else
		update(v * 2 + 1, m + 1, r, p, val);
	t[v] = t[v * 2] + t[v * 2 + 1];
}

int query(int v,int l,int r,int i,int j)
{
	if (i == l && r == j)
		return t[v];
	int m = (l + r) / 2;
	if (j <= m)
		return query(v * 2, l, m, i, j);
	else if(i>=i+1)
		return query(v * 2+1, m+1, r, i, j);
	else
		return query(v * 2, l, m, i, m)+ query(v * 2 + 1, m + 1, r, m+1, j);
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 1; i < n; i++)
		if (a[i - 1] < a[i])
		{
			update(1,0,1000000,a[i-1],1);
			update(1,0,1000000,a[i],-1);
		}
		else if (a[i - 1] > a[i])
		{
			update(1, 0, 1000000, a[i], 1);
			update(1, 0, 1000000, a[i - 1], -1);
		}

	for (int j = 0; j < m; j++)
	{
		int t;
		cin >> t;
		if (t == 1)
		{
			int p, v;
			cin >> p >> v; p--;
			for (int i = max(1, p); i < min(n, p + 2); i++)
				if (a[i - 1] < a[i])
				{
					update(1, 0, 1000000, a[i - 1], -1);
					update(1, 0, 1000000, a[i], 1);
				}
				else if (a[i - 1] > a[i])
				{
					update(1, 0, 1000000, a[i], -1);
					update(1, 0, 1000000, a[i - 1], 1);
				}

			a[p] = v;
			for (int i = max(1, p); i < min(n, p + 2); i++)
				if (a[i - 1] < a[i])
				{
					update(1, 0, 1000000, a[i - 1], 1);
					update(1, 0, 1000000, a[i], -1);
				}
				else if (a[i - 1] > a[i])
				{
					update(1, 0, 1000000, a[i], 1);
					update(1, 0, 1000000, a[i - 1], -1);
				}
		}
		else
		{
			int h;
			cin >> h;
			cout << query(1, 0, 1000000, 0, h) << endl;
		}
	}

	return 0;
}

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