제출 #136187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
136187		FedericoS	Simple game (IZhO17_game)	C++14	22 / 100	1063 ms	10104 KiB

game

#include <iostream>
#include <set>
using namespace std;
typedef pair<int,int> pii;

int N,M;
int H[100005];
int t,x,y;
multiset<int> A,B;

multiset<pii> P;

void add(int i){
	if(i==-1 or i==N-1)
		return;

	int a=H[i];
	int b=H[i+1];
	if(a>b)
		swap(a,b);

	A.insert(a);
	B.insert(b);

}

void remove(int i){
	if(i==-1 or i==N-1)
		return;

	int a=H[i];
	int b=H[i+1];
	if(a>b)
		swap(a,b);

	A.erase(A.find(a));
	B.erase(B.find(b));

}

int query(int h){

	int res=0;

	for(int x:A)
		if(x<h)
			res++;
	for(int x:B)
		if(x<h)
			res--;

	return res;

}

/*
void print(){
	cout<<"******\n";

	cout<<"startUp   ";
	for(int x:startUp)
		cout<<x<<" ";
	cout<<"\n";

	cout<<"startDown ";
	for(int x:startDown)
		cout<<x<<" ";
	cout<<"\n";

	cout<<"endUp     ";
	for(int x:endUp)
		cout<<x<<" ";
	cout<<"\n";

	cout<<"endDown   ";
	for(int x:endDown)
		cout<<x<<" ";
	cout<<"\n";

	cout<<"******\n";
}
*/

int main(){
	cin>>N>>M;
	for(int i=0;i<N;i++)
		cin>>H[i];

	for(int i=0;i<N-1;i++)
		add(i);

	while(M--){

		cin>>t;

		if(t==1){
			cin>>x>>y;
			x--;
			remove(x-1);
			remove(x);
			H[x]=y;
			add(x-1);
			add(x);
		}
		else{
			cin>>x;
			cout<<query(x)<<"\n";
		}
	}

}

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