oj.uz

Submission #136182

# Submission time Handle Problem Language Result Execution time Memory
136182 2019-07-24T22:47:17 Z FedericoS Simple game (IZhO17_game) C++14
22 / 100
 1000 ms 10812 KB 
#include <iostream>
#include <set>
using namespace std;

int N,M;
int H[100005];
int t,x,y;
multiset<int> startUp, startDown, endUp, endDown;

void add(int i){
	if(i==-1 or i==N-1)
		return;
	if(H[i]<H[i+1]){
		startUp.insert(H[i]);
		endUp.insert(H[i+1]);
	}
	else{
		startDown.insert(H[i]);
		endDown.insert(H[i+1]);	
	}
}

void remove(int i){
	if(i==-1 or i==N-1)
		return;
	if(H[i]<H[i+1]){
		startUp.erase(H[i]);
		endUp.erase(H[i+1]);
	}
	else{
		startDown.erase(H[i]);
		endDown.erase(H[i+1]);	
	}
}

int query(int h){

	int res=0;
	for(int i=0;i<N-1;i++)
		if((H[i]<h and h<H[i+1]) or (H[i+1]<h and h<H[i]))
			res++;
	return res;

	/*

	int a,b,res=0;

	a=b=0;
	for(int x:startUp)
		if(x<h)
			a++;
	for(int x:endUp)
		if(x<h)
			b++;
	res+=a-b;

	a=b=0;
	for(int x:startDown)
		if(x>h)
			a++;
	for(int x:endDown)
		if(x>h)
			b++;
	res+=a-b;

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 8 ms 376 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 8 ms 380 KB Output is correct
7 Correct 7 ms 376 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 8 ms 376 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 8 ms 380 KB Output is correct
7 Correct 7 ms 376 KB Output is correct
8 Execution timed out 1073 ms 10812 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 8 ms 376 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 8 ms 380 KB Output is correct
7 Correct 7 ms 376 KB Output is correct
8 Execution timed out 1073 ms 10812 KB Time limit exceeded
9 Halted 0 ms 0 KB -