Submission #588690

#	Time	Username	Problem	Language	Result	Execution time	Memory
588690		peuch	Event Hopping (BOI22_events)	C++17	10 / 100	102 ms	17500 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;
vector<int> *dist[MAXN];

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++){
//		printf("Adding event: %d %d\n", line[i].s, line[i].e);
		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];
//		printf("\t -> %d\n", ini);
		if(i == ini) dist[i] = new vector<int>;
		else dist[i] = dist[ini];
		while(!dist[i]->empty() && dist[i]->back() > line[i].s)
			dist[i]->pop_back();
		dist[i]->push_back(line[i].s);
//		printf("\t");
//		for(int j = 0; j < dist[i].size(); j++)
//			printf("%d ", dist[i][j]);
//		printf("\n");
		for(int j = 0; j < ar[line[i].id].size(); j++){
//			printf("Query event: %d %d %d\n", ar[line[i].id][j].l, ar[line[i].id][j].r, ar[line[i].id][j].id);
			if(ar[line[i].id][j].l > ar[line[i].id][j].r) continue;
			int k = upper_bound(dist[i]->begin(), dist[i]->end(), ar[line[i].id][j].l) - dist[i]->begin() - 1;
//			printf("\t%d\n", k);
			if(k < 0) continue;
			ans[ar[line[i].id][j].id] = dist[i]->size() - k;
		}
//		for(int j = 0; j <= i; j++){
//			printf("dist[%d] = ", j);
//			for(int k = 0; k < dist[j].size(); k++)
//				printf("%d ", dist[j][k]);
//			printf("\n");
//		}
	}
	
	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:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i = 0; i < line.size(); i++){
      |                 ~~^~~~~~~~~~~~~
events.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int j = 0; j < ar[line[i].id].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~
events.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
events.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d %d", &s[i], &e[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
events.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%d %d", &ini, &fim);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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