oj.uz

Submission #136189

# Submission time Handle Problem Language Result Execution time Memory
136189 2019-07-24T23:18:29 Z FedericoS Simple game (IZhO17_game) C++14
100 / 100
 884 ms 15640 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<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int N,M;
int H[100005];
int t,x,y;
pbds 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){
	return A.order_of_key({h,-1})-B.order_of_key({h,-1});
}


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 7 ms 504 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 7 ms 504 KB Output is correct
7 Correct 6 ms 376 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 7 ms 504 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 7 ms 504 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 501 ms 13736 KB Output is correct
9 Correct 733 ms 15440 KB Output is correct
10 Correct 682 ms 15580 KB Output is correct
11 Correct 479 ms 14224 KB Output is correct
12 Correct 659 ms 15200 KB Output is correct
13 Correct 612 ms 15300 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 7 ms 504 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 7 ms 504 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 501 ms 13736 KB Output is correct
9 Correct 733 ms 15440 KB Output is correct
10 Correct 682 ms 15580 KB Output is correct
11 Correct 479 ms 14224 KB Output is correct
12 Correct 659 ms 15200 KB Output is correct
13 Correct 612 ms 15300 KB Output is correct
14 Correct 846 ms 15524 KB Output is correct
15 Correct 848 ms 15640 KB Output is correct
16 Correct 884 ms 15608 KB Output is correct
17 Correct 837 ms 15640 KB Output is correct
18 Correct 841 ms 15568 KB Output is correct