oj.uz

Submission #588690

# Submission time Handle Problem Language Result Execution time Memory
588690 2022-07-03T21:12:27 Z peuch Event Hopping (BOI22_events) C++17
10 / 100
 102 ms 17500 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 68 ms 8984 KB Output is correct
3 Correct 69 ms 10104 KB Output is correct
4 Correct 80 ms 10600 KB Output is correct
5 Correct 70 ms 11292 KB Output is correct
6 Correct 70 ms 12516 KB Output is correct
7 Correct 70 ms 12092 KB Output is correct
8 Correct 73 ms 16788 KB Output is correct
9 Correct 69 ms 17500 KB Output is correct
10 Correct 77 ms 12224 KB Output is correct
11 Correct 85 ms 13456 KB Output is correct
12 Correct 58 ms 15136 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 2 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 2 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 81 ms 9252 KB Output is correct
2 Correct 72 ms 11832 KB Output is correct
3 Correct 102 ms 10528 KB Output is correct
4 Correct 68 ms 15692 KB Output is correct
5 Correct 78 ms 10972 KB Output is correct
6 Incorrect 88 ms 10544 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 68 ms 8984 KB Output is correct
3 Correct 69 ms 10104 KB Output is correct
4 Correct 80 ms 10600 KB Output is correct
5 Correct 70 ms 11292 KB Output is correct
6 Correct 70 ms 12516 KB Output is correct
7 Correct 70 ms 12092 KB Output is correct
8 Correct 73 ms 16788 KB Output is correct
9 Correct 69 ms 17500 KB Output is correct
10 Correct 77 ms 12224 KB Output is correct
11 Correct 85 ms 13456 KB Output is correct
12 Correct 58 ms 15136 KB Output is correct
13 Incorrect 2 ms 2644 KB Output isn't correct
14 Halted 0 ms 0 KB -