Submission #588704

#	Time	Username	Problem	Language	Result	Execution time	Memory
588704		peuch	Event Hopping (BOI22_events)	C++17	20 / 100	91 ms	14068 KiB

events

#include<bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e5 + 10;
const int INF = 1e9;
 
int n, q;
int s[MAXN], e[MAXN];
int ans[MAXN];
 
struct event{
	int s, e, id;
	event(int _s, int _e, int _id) {
		s = _s;
		e = _e;
		id = _id;
	}
	bool operator < (event x){
		if(e == x.e) return s < x.s;
		return e < x.e;
	}
};
 
struct query{
	int l, r, id;
	query(int _l, int _r, int _id){
		l = _l;
		r = _r;
		id = _id;
	}
};
 
vector<query> ar[MAXN];
 
vector<event> line;
int point[MAXN];
vector<vector<int> > dist;
 
int main(){
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; i++){
		scanf("%d %d", &s[i], &e[i]);
		line.push_back(event(s[i], e[i], i));
	}
	for(int i = 1; i <= q; i++){
		int ini, fim;
		scanf("%d %d", &ini, &fim);
		ans[i] = INF;
		if(ini == fim) ans[i] = 0;
		else ar[fim].push_back(query(e[ini], e[fim], i));
	}
	
	sort(line.begin(), line.end());
	
	vector<int> pilha;
	for(int i = 0; i < line.size(); i++){
		while(!pilha.empty() && line[pilha.back()].s >= line[i].s){
			pilha.pop_back();
		}
		pilha.push_back(i);
		
		int ini = 0, fim = pilha.size() - 1;
		while(ini != fim){
			int mid = (ini + fim) >> 1;
			if(line[pilha[mid]].e >= line[i].s) fim = mid;
			else ini = mid + 1;
		}
		ini = pilha[ini];
		if(ini == i){
			point[i] = dist.size();
			dist.push_back(vector<int> (0));
		}
		else point[i] = point[ini];
		while(dist[point[i]].size() != 0 && dist[point[i]].back() > line[ini].s)
			dist[point[i]].pop_back();
		dist[point[i]].push_back(line[i].s);
		for(int j = 0; j < ar[line[i].id].size(); j++){
			if(ar[line[i].id][j].l > ar[line[i].id][j].r) continue;
			int k = upper_bound(dist[point[i]].begin(), dist[point[i]].end(), ar[line[i].id][j].l) - dist[point[i]].begin() - 1;
			if(k < 0) continue;
			ans[ar[line[i].id][j].id] = dist[point[i]].size() - k;
		}
	}
	
	for(int i = 1; i <= q; i++){
		if(ans[i] == INF) printf("impossible\n");
		else printf("%d\n", ans[i]);
	}
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i = 0; i < line.size(); i++){
      |                 ~~^~~~~~~~~~~~~
events.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int j = 0; j < ar[line[i].id].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~
events.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
events.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d %d", &s[i], &e[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
events.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   scanf("%d %d", &ini, &fim);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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