oj.uz

Submission #588691

# Submission time Handle Problem Language Result Execution time Memory
588691 2022-07-03T21:15:57 Z peuch Event Hopping (BOI22_events) C++17
10 / 100
 97 ms 15232 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 70 ms 8804 KB Output is correct
3 Correct 70 ms 9220 KB Output is correct
4 Correct 89 ms 9156 KB Output is correct
5 Correct 67 ms 9788 KB Output is correct
6 Correct 69 ms 10236 KB Output is correct
7 Correct 72 ms 10380 KB Output is correct
8 Correct 70 ms 15176 KB Output is correct
9 Correct 69 ms 15092 KB Output is correct
10 Correct 75 ms 10028 KB Output is correct
11 Correct 81 ms 11948 KB Output is correct
12 Correct 55 ms 14628 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8740 KB Output is correct
2 Correct 69 ms 9204 KB Output is correct
3 Correct 84 ms 9096 KB Output is correct
4 Correct 77 ms 15232 KB Output is correct
5 Correct 97 ms 10028 KB Output is correct
6 Incorrect 83 ms 10040 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 2644 KB Output is correct
2 Correct 70 ms 8804 KB Output is correct
3 Correct 70 ms 9220 KB Output is correct
4 Correct 89 ms 9156 KB Output is correct
5 Correct 67 ms 9788 KB Output is correct
6 Correct 69 ms 10236 KB Output is correct
7 Correct 72 ms 10380 KB Output is correct
8 Correct 70 ms 15176 KB Output is correct
9 Correct 69 ms 15092 KB Output is correct
10 Correct 75 ms 10028 KB Output is correct
11 Correct 81 ms 11948 KB Output is correct
12 Correct 55 ms 14628 KB Output is correct
13 Incorrect 1 ms 2644 KB Output isn't correct
14 Halted 0 ms 0 KB -