oj.uz

Submission #750521

# Submission time Handle Problem Language Result Execution time Memory
750521 2023-05-29T15:36:08 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 182 ms 19860 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].begin(),addy[i].end());
		sort(quer[i].rbegin(),quer[i].rend());
		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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 105 ms 13984 KB Output is correct
3 Correct 112 ms 13616 KB Output is correct
4 Correct 112 ms 13656 KB Output is correct
5 Correct 110 ms 14052 KB Output is correct
6 Correct 110 ms 14584 KB Output is correct
7 Correct 110 ms 14684 KB Output is correct
8 Correct 122 ms 19784 KB Output is correct
9 Correct 112 ms 19860 KB Output is correct
10 Correct 141 ms 14516 KB Output is correct
11 Correct 150 ms 16476 KB Output is correct
12 Correct 63 ms 12092 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 456 KB Output isn't correct
8 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 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 456 KB Output isn't correct
8 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 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 456 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 14072 KB Output is correct
2 Correct 133 ms 13676 KB Output is correct
3 Correct 113 ms 13504 KB Output is correct
4 Correct 113 ms 19656 KB Output is correct
5 Correct 163 ms 14432 KB Output is correct
6 Incorrect 182 ms 18116 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 105 ms 13984 KB Output is correct
3 Correct 112 ms 13616 KB Output is correct
4 Correct 112 ms 13656 KB Output is correct
5 Correct 110 ms 14052 KB Output is correct
6 Correct 110 ms 14584 KB Output is correct
7 Correct 110 ms 14684 KB Output is correct
8 Correct 122 ms 19784 KB Output is correct
9 Correct 112 ms 19860 KB Output is correct
10 Correct 141 ms 14516 KB Output is correct
11 Correct 150 ms 16476 KB Output is correct
12 Correct 63 ms 12092 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 320 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 1 ms 456 KB Output isn't correct
20 Halted 0 ms 0 KB -