#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef int ll;
struct one{
ll first, second, ind;
};
bool cmp(one p1, one p2){
if(p1.second == p2.second)
return p1.first < p2.first;
return p1.second < p2.second;
}
void compress(vector<one> &a){
vector<ll>b;
for(auto i: a){
b.push_back(i.first);
b.push_back(i.second);
}
sort(b.begin(), b.end());
b.resize(unique(b.begin(), b.end()) - b.begin());
ll step = 1;
map<ll, ll> mp;
for(auto i: b)
mp[i] = step++;
for(auto &i: a){
i.first = mp[i.first];
i.second = mp[i.second];
}
}
ll dp[2 * 5007][2 * 5007];
vector<ll>start_here[2 * 5007];
vector<one>a;
void count_dp(one fin){
for(int i = 0; i < a.size(); i++)
dp[i][fin.ind] = 1e9;
dp[fin.ind][fin.ind] = 0;
bool ok = false;
multiset<ll>st;
for(int ind = a.size() - 1; ind >= 0; ind--){
auto i = a[ind];
if(i.ind == fin.ind){
//cout << i.ind << ' ' << ind << endl;
ok = true;
st.insert(0);
}
else if(ok){
if(st.empty()){
// cout << "st.empty() " << i.ind << endl;
dp[i.ind][fin.ind] = 1e9;
}
else{
// cout << i.ind << endl;
// for(auto j: st)
// cout << j << ' ';
// cout << endl;
dp[i.ind][fin.ind] = *st.begin();
dp[i.ind][fin.ind]++;
st.insert(dp[i.ind][fin.ind]);
}
}
else{
// cout << "not yet " << i.ind << endl;
}
if(ind - 1 >= 0){
for(int del = i.second; del > a[ind - 1].second; del--)
for(auto j: start_here[del]){
if(st.find(dp[j][fin.ind]) != st.end())
st.erase(st.find(dp[j][fin.ind]));
}
}
}
}
vector<ll>count_dp2(ll start){
vector<ll>dp2(a.size(), 1e9);
dp2[start] = 0;
for(auto i: a){
for(auto j: a){
if(i.first <= j.second && j.second <= i.second){
dp2[i.ind] = min(dp2[i.ind], dp2[j.ind] + 1);
}
}
}
return dp2;
}
#define endl '\n'
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, q;
cin >> n >> q;
a.resize(n);
for(int i = 0; i < n; i++){
cin >> a[i].first >> a[i].second;
a[i].ind = i;
}
compress(a);
sort(a.begin(), a.end(), cmp);
for(auto i: a)
start_here[i.first].push_back(i.ind);
for(auto i: a){
count_dp(i);
}
while(q--){
ll l, r;
cin >> l >> r;
//l = 1 + rand() % n, r = 1 + rand() % n;
l--, r--;
//auto dp2 = count_dp2(l);
if(dp[l][r] == (ll)(1e9))
cout << "impossible" << endl;
else{
cout << dp[l][r] << endl;
}
}
return 0;
}
/*
8 1
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 7
*/
/*
1 2
1 1000000000
*/
/*
5 9
2 0
*/
/*
10 100
1 3
4 6
2 8
8 23
1 4
2 4
6 73
2 34
1 9
8 90
2 3
*/
Compilation message
events.cpp: In function 'void count_dp(one)':
events.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<one>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Runtime error |
242 ms |
99724 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
596 KB |
Output is correct |
3 |
Correct |
32 ms |
8532 KB |
Output is correct |
4 |
Correct |
25 ms |
8640 KB |
Output is correct |
5 |
Correct |
30 ms |
8532 KB |
Output is correct |
6 |
Correct |
50 ms |
8600 KB |
Output is correct |
7 |
Correct |
86 ms |
8664 KB |
Output is correct |
8 |
Correct |
57 ms |
8672 KB |
Output is correct |
9 |
Correct |
56 ms |
8592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
596 KB |
Output is correct |
3 |
Correct |
32 ms |
8532 KB |
Output is correct |
4 |
Correct |
25 ms |
8640 KB |
Output is correct |
5 |
Correct |
30 ms |
8532 KB |
Output is correct |
6 |
Correct |
50 ms |
8600 KB |
Output is correct |
7 |
Correct |
86 ms |
8664 KB |
Output is correct |
8 |
Correct |
57 ms |
8672 KB |
Output is correct |
9 |
Correct |
56 ms |
8592 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
36 ms |
8628 KB |
Output is correct |
13 |
Correct |
22 ms |
8632 KB |
Output is correct |
14 |
Correct |
32 ms |
8576 KB |
Output is correct |
15 |
Correct |
55 ms |
8616 KB |
Output is correct |
16 |
Correct |
87 ms |
8660 KB |
Output is correct |
17 |
Correct |
47 ms |
8660 KB |
Output is correct |
18 |
Correct |
48 ms |
8604 KB |
Output is correct |
19 |
Execution timed out |
1524 ms |
120136 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
596 KB |
Output is correct |
3 |
Correct |
32 ms |
8532 KB |
Output is correct |
4 |
Correct |
25 ms |
8640 KB |
Output is correct |
5 |
Correct |
30 ms |
8532 KB |
Output is correct |
6 |
Correct |
50 ms |
8600 KB |
Output is correct |
7 |
Correct |
86 ms |
8664 KB |
Output is correct |
8 |
Correct |
57 ms |
8672 KB |
Output is correct |
9 |
Correct |
56 ms |
8592 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
31 ms |
8628 KB |
Output is correct |
13 |
Correct |
28 ms |
8532 KB |
Output is correct |
14 |
Correct |
33 ms |
8616 KB |
Output is correct |
15 |
Correct |
49 ms |
8532 KB |
Output is correct |
16 |
Correct |
90 ms |
8660 KB |
Output is correct |
17 |
Correct |
50 ms |
8664 KB |
Output is correct |
18 |
Correct |
56 ms |
8588 KB |
Output is correct |
19 |
Runtime error |
281 ms |
99664 KB |
Execution killed with signal 11 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
243 ms |
99680 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Runtime error |
242 ms |
99724 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |