oj.uz

Submission #588703

# Submission time Handle Problem Language Result Execution time Memory
588703 2022-07-03T21:47:23 Z peuch Event Hopping (BOI22_events) C++17
10 / 100
 86 ms 14076 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;
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];
		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

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:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 75 ms 8288 KB Output is correct
3 Correct 69 ms 8836 KB Output is correct
4 Correct 86 ms 8836 KB Output is correct
5 Correct 68 ms 9404 KB Output is correct
6 Correct 67 ms 10108 KB Output is correct
7 Correct 73 ms 9964 KB Output is correct
8 Correct 72 ms 14008 KB Output is correct
9 Correct 70 ms 14076 KB Output is correct
10 Correct 75 ms 9604 KB Output is correct
11 Correct 77 ms 11712 KB Output is correct
12 Correct 52 ms 13272 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 74 ms 8392 KB Output is correct
2 Correct 74 ms 8844 KB Output is correct
3 Correct 79 ms 8784 KB Output is correct
4 Correct 68 ms 14012 KB Output is correct
5 Correct 79 ms 9688 KB Output is correct
6 Incorrect 86 ms 9556 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 75 ms 8288 KB Output is correct
3 Correct 69 ms 8836 KB Output is correct
4 Correct 86 ms 8836 KB Output is correct
5 Correct 68 ms 9404 KB Output is correct
6 Correct 67 ms 10108 KB Output is correct
7 Correct 73 ms 9964 KB Output is correct
8 Correct 72 ms 14008 KB Output is correct
9 Correct 70 ms 14076 KB Output is correct
10 Correct 75 ms 9604 KB Output is correct
11 Correct 77 ms 11712 KB Output is correct
12 Correct 52 ms 13272 KB Output is correct
13 Incorrect 1 ms 2644 KB Output isn't correct
14 Halted 0 ms 0 KB -