oj.uz

Submission #750525

# Submission time Handle Problem Language Result Execution time Memory
750525 2023-05-29T15:42:16 Z vjudge1 Event Hopping (BOI22_events) C++17
0 / 100
 172 ms 19296 KB 
#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(ppp,make_pair(i,pp)));	
		if(l==r){
			res[i]=2;
		}
	}
	vector<pair<int,int>>v;
	vector<int>vv;
	for(int i=0;i<sz;i++){
		sort(addy[i].rbegin(),addy[i].rend());
		sort(quer[i].begin(),quer[i].end());
		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){
				//hichy;
			}
			else{
				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());
				}
			}
			while(quer[i].size()>0&&quer[i].back().first==x){
			auto y=quer[i].back();
			swap(y.first,y.second.second);
			quer[i].pop_back();
			if(res[y.second.first]==2){
				res[y.second.first]=0;
				continue;
			}
			int z=lower_bound(v.begin(),v.end(),make_pair(y.first+1,-1))-v.begin();
			z--;
			if(y.first>i||((int)vv.size()>0&&vv.back()>z+1)){
				res[y.second.first]=-1;
				continue;
			}
			if(y.first<=i&&y.first>=y.second.second){
				res[y.second.first]=1;
				continue;
			}
			//cout<<i<<" "<<allind[i]<<" "<<vv.back()<<" "<<z<<"\n";
			res[y.second.first]=1+(int)v.size()-1-z;
			if(y.second.second!=v.back().first){
				if(z==(int)v.size()-1||((int)v.size()>1&&v[(int)v.size()-2].second<y.second.second)){
					res[y.second.first]++;
				}
			}
		}
		}
	}
	for(int i=0;i<m;i++){
		if(res[i]==-1){
			cout<<"impossible\n";
		}
		else{
			cout<<res[i]<<"\n";
		}
	}
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:49: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]
   49 |     if((int)vv.size()>0&&vv.back()==v.size()){
      |                          ~~~~~~~~~^~~~~~~~~~
events.cpp:55: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]
   55 |     if((int)vv.size()>0&&vv.back()==v.size()){
      |                          ~~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 13672 KB Output is correct
2 Correct 141 ms 13216 KB Output is correct
3 Correct 114 ms 13136 KB Output is correct
4 Correct 159 ms 19296 KB Output is correct
5 Correct 169 ms 14092 KB Output is correct
6 Incorrect 172 ms 17864 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -