oj.uz

Submission #136188

# Submission time Handle Problem Language Result Execution time Memory
136188 2019-07-24T23:16:49 Z FedericoS Simple game (IZhO17_game) C++14
22 / 100
 1000 ms 10104 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
#include <set>
using namespace std;
using namespace __gnu_pbds;
typedef pair<int,int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

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

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,c++});
	B.insert({b,c++});

}

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.lower_bound({a,-1}));
	B.erase(B.lower_bound({b,-1}));

}

int query(int h){

	int res=0;

	for(pii x:A)
		if(x.first<h)
			res++;
	for(pii x:B)
		if(x.first<h)
			res--;

	return res;

}


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

	cout<<"A ";
	for(pii x:A)
		cout<<x.first<<","<<x.second<<" ";
	cout<<"\n";

	cout<<"B ";
	for(pii x:B)
		cout<<x.first<<","<<x.second<<" ";
	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 376 KB Output is correct
2 Correct 17 ms 376 KB Output is correct
3 Correct 17 ms 376 KB Output is correct
4 Correct 17 ms 376 KB Output is correct
5 Correct 18 ms 376 KB Output is correct
6 Correct 17 ms 380 KB Output is correct
7 Correct 25 ms 376 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 17 ms 376 KB Output is correct
3 Correct 17 ms 376 KB Output is correct
4 Correct 17 ms 376 KB Output is correct
5 Correct 18 ms 376 KB Output is correct
6 Correct 17 ms 380 KB Output is correct
7 Correct 25 ms 376 KB Output is correct
8 Execution timed out 1075 ms 10104 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 376 KB Output is correct
2 Correct 17 ms 376 KB Output is correct
3 Correct 17 ms 376 KB Output is correct
4 Correct 17 ms 376 KB Output is correct
5 Correct 18 ms 376 KB Output is correct
6 Correct 17 ms 380 KB Output is correct
7 Correct 25 ms 376 KB Output is correct
8 Execution timed out 1075 ms 10104 KB Time limit exceeded
9 Halted 0 ms 0 KB -