#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
vector<vector<int> >num;
vector<pair<int , int > >cmp;
vector<int>pow2;
int ind[200000] , platz[200000];
int lift[300000][20], seg[20][800000];
unordered_map<int , int>trans;
int sucher(int id , int l , int r , int gewl , int gewr , int ver){
if(gewl > r || l > gewr){
return mod;
}
if(gewl <= l && r <= gewr){
return seg[ver][id];
}
int m = (l + r)/2;
return min(sucher(id * 2 , l , m , gewl , gewr , ver) , sucher(id * 2 + 1 , m + 1 , r , gewl ,gewr , ver));
}
int main(){
int menge , numm , nummer , que , len;
cin >> menge >> que;
for(int i = 1 ; i < 1000000 ; i*= 2){
pow2.push_back(i);
}
for(len = 1 ; len < 100000 ; len *= 2);
for(int i = 0 ; i < menge ; i++){
platz[i + 1] = -1;
cin >> numm >> nummer;
num.push_back({nummer , numm , i + 1});
cmp.push_back({numm , 0});
cmp.push_back({nummer , 1});
}
int pl = 0;// does matter sort begin?
sort(cmp.begin() , cmp.end());
sort(num.begin() , num.end());
for(int i = cmp.size() - 1 ; i >= 0; i--){
if(trans[cmp[i].first] == 0 && cmp[i].second == 1){
// cout << cmp[i].first << ' ';
pl++;
}//////////////////////////////////////////////////////////////
trans[cmp[i].first] = pl;
}
pl++;
// cout << "\n";
for(int i = 0 ; i < num.size() ; i++){
// cout << num[i][0] << ' ' << num[i][1] << "\n";
num[i][0] = pl - trans[num[i][0]];
num[i][1] = pl - trans[num[i][1]];
ind[num[i][2]] = i;
if(platz[num[i][0]] == -1){
platz[num[i][0]] = i;
}
lift[i][0] = num[i][1];
// cout << num[i][0]<< ' ' << num[i][1]<< "\n\n";
}
for(int i = 1 ; i < 20 ; i++){
// cout << i << ' ';
// for(int j = 0 ; j < 100000; j++){
// seg[i - 1][j + len] = lift[j][i - 1];
// }
for(int j = len - 1 ; j > 0 ; j--){
seg[i - 1][j] = min(seg[i - 1][j * 2] , seg[i - 1][j * 2 + 1]);
}
for(int j = 0 ; j < num.size(); j++){
lift[j][i] = sucher(1 , 1 , len , platz[lift[j][i - 1]] + 1 , j + 1 , i - 1);
}
// cout << i << " \n";
}
// for(int i = 0 ; i < menge ; i++){
// for(int j = 0 ; j < 20 ; j++){
// cout << lift[i][j] << ' ';
// }
// cout << "\n";
// }
int erg;
while(que--){
erg = 0;
cin >> numm >> nummer;
if(numm == nummer){
cout << 0 << "\n";
continue;
}
numm = ind[numm];
nummer = ind[nummer];
// cout << numm <<' ' << nummer << "\n";
if(numm > nummer){
cout << "impossible\n";
continue;
}
int be = nummer , en = nummer;
for(int i = 19 ; i >= 0 ; i--){
int comp = sucher(1 , 1, len , be + 1 , en + 1 , i ) ;
// cout << comp << " ";
if( comp > num[numm][0]){
// cout << i << ' ' ;
erg += pow2[i];
be = platz[comp];
}
}
// cout << "\n";
// cout << nummer << " \n";
be = platz[sucher(1 , 1, len , be + 1 , en + 1 , 0 )];
// cout << numm << ' ' << be << ' ' << en << "\n";
if(numm >= be){
cout << erg + 1 << "\n";
}
else{
cout << "impossible\n";
}
}
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0 ; i < num.size() ; i++){
| ~~^~~~~~~~~~~~
events.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int j = 0 ; j < num.size(); j++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
10148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
10148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
10148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
792 ms |
30868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
