Submission #386352

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
386352	2021-04-06T12:31:20 Z	vanic	Simple game (IZhO17_game)	C++14	100 / 100	78 ms	6924 KB

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.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	4 ms	4076 KB	Output is correct
3	Correct	3 ms	4076 KB	Output is correct
4	Correct	4 ms	4076 KB	Output is correct
5	Correct	4 ms	4076 KB	Output is correct
6	Correct	4 ms	4076 KB	Output is correct
7	Correct	2 ms	364 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	4 ms	4076 KB	Output is correct
3	Correct	3 ms	4076 KB	Output is correct
4	Correct	4 ms	4076 KB	Output is correct
5	Correct	4 ms	4076 KB	Output is correct
6	Correct	4 ms	4076 KB	Output is correct
7	Correct	2 ms	364 KB	Output is correct
8	Correct	40 ms	1772 KB	Output is correct
9	Correct	52 ms	6892 KB	Output is correct
10	Correct	52 ms	6892 KB	Output is correct
11	Correct	39 ms	1644 KB	Output is correct
12	Correct	44 ms	2924 KB	Output is correct
13	Correct	44 ms	2796 KB	Output is correct

Subtask #3

51.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	4 ms	4076 KB	Output is correct
3	Correct	3 ms	4076 KB	Output is correct
4	Correct	4 ms	4076 KB	Output is correct
5	Correct	4 ms	4076 KB	Output is correct
6	Correct	4 ms	4076 KB	Output is correct
7	Correct	2 ms	364 KB	Output is correct
8	Correct	40 ms	1772 KB	Output is correct
9	Correct	52 ms	6892 KB	Output is correct
10	Correct	52 ms	6892 KB	Output is correct
11	Correct	39 ms	1644 KB	Output is correct
12	Correct	44 ms	2924 KB	Output is correct
13	Correct	44 ms	2796 KB	Output is correct
14	Correct	66 ms	6872 KB	Output is correct
15	Correct	65 ms	6892 KB	Output is correct
16	Correct	73 ms	6912 KB	Output is correct
17	Correct	65 ms	6892 KB	Output is correct
18	Correct	78 ms	6924 KB	Output is correct