oj.uz

Submission #91344

# Submission time Handle Problem Language Result Execution time Memory
91344 2018-12-27T08:01:22 Z davitmarg Simple game (IZhO17_game) C++17
100 / 100
 359 ms 16440 KB 
/*
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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 10 ms 7420 KB Output is correct
3 Correct 10 ms 7420 KB Output is correct
4 Correct 9 ms 7488 KB Output is correct
5 Correct 10 ms 7560 KB Output is correct
6 Correct 10 ms 7616 KB Output is correct
7 Correct 5 ms 7616 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 10 ms 7420 KB Output is correct
3 Correct 10 ms 7420 KB Output is correct
4 Correct 9 ms 7488 KB Output is correct
5 Correct 10 ms 7560 KB Output is correct
6 Correct 10 ms 7616 KB Output is correct
7 Correct 5 ms 7616 KB Output is correct
8 Correct 214 ms 7616 KB Output is correct
9 Correct 301 ms 12464 KB Output is correct
10 Correct 308 ms 13964 KB Output is correct
11 Correct 199 ms 13964 KB Output is correct
12 Correct 252 ms 13964 KB Output is correct
13 Correct 247 ms 13964 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 10 ms 7420 KB Output is correct
3 Correct 10 ms 7420 KB Output is correct
4 Correct 9 ms 7488 KB Output is correct
5 Correct 10 ms 7560 KB Output is correct
6 Correct 10 ms 7616 KB Output is correct
7 Correct 5 ms 7616 KB Output is correct
8 Correct 214 ms 7616 KB Output is correct
9 Correct 301 ms 12464 KB Output is correct
10 Correct 308 ms 13964 KB Output is correct
11 Correct 199 ms 13964 KB Output is correct
12 Correct 252 ms 13964 KB Output is correct
13 Correct 247 ms 13964 KB Output is correct
14 Correct 340 ms 16184 KB Output is correct
15 Correct 348 ms 16184 KB Output is correct
16 Correct 355 ms 16440 KB Output is correct
17 Correct 359 ms 16440 KB Output is correct
18 Correct 336 ms 16440 KB Output is correct