Submission #750424

#	Time	Username	Problem	Language	Result	Execution time	Memory
750424		vjudge1	Event Hopping (BOI22_events)	C++17	10 / 100	182 ms	19380 KiB

events

#include<bits/stdc++.h>
using namespace std;
int sz=0;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	int n,m;
	cin>>n>>m;
	vector<int>allind;
	vector<pair<int,int>>all(n);
	for(int i=0;i<n;i++){
		cin>>all[i].first>>all[i].second;
		allind.push_back(all[i].first);
		allind.push_back(all[i].second);
	}
	sort(allind.begin(),allind.end());
	allind.resize(unique(allind.begin(),allind.end())-allind.begin());
	sz=(int)allind.size();
	vector<vector<pair<int,pair<int,int>>>>quer(sz+10);
	vector<vector<int>>addy(sz+1);
	for(int i=0;i<n;i++){
		int p=lower_bound(allind.begin(),allind.end(),all[i].second)-allind.begin();
		int pp=lower_bound(allind.begin(),allind.end(),all[i].first)-allind.begin();
		addy[p].push_back(pp);
	}
	vector<int>res(m+10);
	for(int i=0;i<m;i++){
		int l,r;
		cin>>l>>r;
		l--;
		r--;
		int ppp=lower_bound(allind.begin(),allind.end(),all[r].first)-allind.begin();
		int p=lower_bound(allind.begin(),allind.end(),all[r].second)-allind.begin();
		int pp=lower_bound(allind.begin(),allind.end(),all[l].second)-allind.begin();
		quer[p].push_back(make_pair(pp,make_pair(i,ppp)));	
		if(l==r){
			res[i]=2;
		}
	}
	vector<pair<int,int>>v;
	vector<int>vv;
	for(int i=0;i<sz;i++){
		for(auto x:addy[i]){
			while((int)v.size()>0&&v.back().first>=x){
				if((int)vv.size()>0&&vv.back()==v.size()){
					vv.pop_back();
				}
				v.pop_back();
			}
			while(v.size()>1&&v[(int)v.size()-2].second>=x){
				if((int)vv.size()>0&&vv.back()==v.size()){
					vv.pop_back();
				}
				v.pop_back();
			}
			if((int)v.size()!=0&&v.back().second==i){
				continue;
			}
			v.push_back(make_pair(x,i));
			if((int)v.size()==1||v[(int)v.size()-2].second<v.back().first){
				vv.push_back((int)v.size());
			}
		}
		//cout<<i<<" "<<allind[i]<<": \n";
		for(auto x:v){
			//cout<<x.first<<" "<<x.second<<"\n";
		}
		for(auto x:vv){
			//cout<<x<<"\n";
		}
		//cout<<"tamam\n";
		for(auto x:quer[i]){
			if(res[x.second.first]==2){
				res[x.second.first]=0;
				continue;
			}
			int z=lower_bound(v.begin(),v.end(),make_pair(x.first+1,-1))-v.begin();
			z--;
			if(x.first>i||((int)vv.size()>0&&vv.back()>z+1)){
				res[x.second.first]=-1;
				continue;
			}
			if(x.first<=i&&x.first>=x.second.second){
				res[x.second.first]=1;
				continue;
			}
			//cout<<i<<" "<<allind[i]<<" "<<vv.back()<<" "<<z<<"\n";
			res[x.second.first]=1+(int)v.size()-1-z;
			if(x.second.second!=v.back().first){
				if(z==(int)v.size()-1||((int)v.size()>1&&v[(int)v.size()-2].second<x.second.second)){
					res[x.second.first]++;
				}
			}
		}
	}
	for(int i=0;i<m;i++){
		if(res[i]==-1){
			cout<<"impossible\n";
		}
		else{
			cout<<res[i]<<"\n";
		}
	}
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:47:35: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if((int)vv.size()>0&&vv.back()==v.size()){
      |                          ~~~~~~~~~^~~~~~~~~~
events.cpp:53:35: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     if((int)vv.size()>0&&vv.back()==v.size()){
      |                          ~~~~~~~~~^~~~~~~~~~
events.cpp:67:12: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   67 |   for(auto x:v){
      |            ^
events.cpp:70:12: warning: unused variable 'x' [-Wunused-variable]
   70 |   for(auto x:vv){
      |            ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30