Submission #588697

#	Time	Username	Problem	Language	Result	Execution time	Memory
588697		peuch	Event Hopping (BOI22_events)	C++17	20 / 100	82 ms	14016 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 dist[MAXN];
int tam[MAXN];

vector<vector<int> > auxPoint;

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