This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int base = 131072;
const int max_long = 20;
pair<int, int> jump_tree[max_long][base*2];
int train[base];
int train_reverse[base];
pair<int, int> get_array(int a, int b, int log, int v = 1, int l = 0, int r = base - 1){
if(a <= l and b >= r){
return jump_tree[log][v];
}
if(a > r or b < l){
return {1e9, 0};
}
int mid = (l+r)/2;
pair<int, int> first = get_array(a, b, log, v * 2, l, mid);
pair<int, int> second = get_array(a, b, log, v * 2 + 1, mid + 1, r);
pair<int, int> result;
result.first = min(first.first, second.first);
result.second = max(first.second, second.second);
return result;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k, m, q;
cin >> n >> k >> m;
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
if(a < b){
train[a] = max(train[a], b);
}else{
train_reverse[a] = min(train_reverse[a], b);
if(train_reverse[a] == 0){
train_reverse[a] = b;
}
}
}
vector<pair<int, int>> actual_trains;
int wsk = 0;
for(int i = 0; i < 2 * base; i++){
jump_tree[0][i] = {1e9, 0};
}
for(int i = 0; i <= n; i++){
int c = train[i];
while(!actual_trains.empty()){
if(actual_trains[actual_trains.size()-1].first < c){
actual_trains.pop_back();
}else{
break;
}
}
if(c != 0){
actual_trains.push_back({c, min(i + k - 1, c)});
}
if(actual_trains.empty()){
jump_tree[0][base + i].second = i;
}else{
if(wsk >= actual_trains.size()){
wsk = actual_trains.size()-1;
}
while(actual_trains[wsk].second < i){
wsk++;
if(wsk == actual_trains.size()){
wsk = 0;
actual_trains.clear();
break;
}
}
if(!actual_trains.empty()){
jump_tree[0][base + i].second = actual_trains[wsk].first;
}else{
jump_tree[0][base + i].second = i;
}
}
}
actual_trains.clear();
for(int i = n; i > 0; i--){
int c = train_reverse[i];
while(!actual_trains.empty()){
if(actual_trains[actual_trains.size()-1].first > c and c != 0){
actual_trains.pop_back();
}else{
break;
}
}
if(c != 0){
actual_trains.push_back({c, max(i - k + 1, c)});
}
if(actual_trains.empty()){
jump_tree[0][base + i].first = i;
}else{
if(wsk >= actual_trains.size()){
wsk = actual_trains.size()-1;
}
while(actual_trains[wsk].second > i){
wsk++;
if(wsk == actual_trains.size()){
wsk = 0;
actual_trains.clear();
break;
}
}
if(!actual_trains.empty()){
jump_tree[0][base + i].first = actual_trains[wsk].first;
}else{
jump_tree[0][base + i].first = i;
}
}
}
for(int i = base - 1; i > 0; i--){
jump_tree[0][i].first = min(jump_tree[0][2*i].first, jump_tree[0][2*i+1].first);
jump_tree[0][i].second = max(jump_tree[0][2*i].second, jump_tree[0][2*i+1].second);
}
for(int i = 1; i < max_long; i++){
for(int j = 1; j <= base + n; j++){
jump_tree[i][j] = get_array(jump_tree[i-1][j].first, jump_tree[i-1][j].second, i - 1);
}
}
cin >> q;
for(int i = 0; i < q; i++){
int begin, end;
cin >> begin >> end;
int result = 0;
int number = (1<<(max_long-1));
pair<int, int> range = {begin, begin};
for(int j = max_long - 1; j >= 0; j--){
pair <int, int> new_range = get_array(range.first, range.second, j);
if(new_range.first > end or new_range.second < end){
result += number;
range = new_range;
}
number /= 2;
}
pair <int, int> new_range_2 = get_array(range.first, range.second, 0);
if(new_range_2.first > end or new_range_2.second < end){
result = -1;
}else{
result++;
}
cout << result << '\n';
}
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | if(wsk >= actual_trains.size()){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | if(wsk == actual_trains.size()){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | if(wsk >= actual_trains.size()){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:106:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | if(wsk == actual_trains.size()){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |