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 "books.h"
#define f first
#define s second
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> tab;
void solve(int a, int b, int &na, int &nb){
//cout<<a<<" "<<b<<" "<<na<<" "<<nb<<'\n';
int ta = na;
int tb = nb;
for(int i = na; i <= a; i++){
if(tab[i].f!=-1){
ta = min(ta, tab[i].f);
tb = max(tb, tab[i].s);
//cout<<i<<" "<<tab[i].f<<" "<<tab[i].s<<'\n';
}
}
for(int i = b; i <= nb; i++){
if(tab[i].f!=-1){
ta = min(ta, tab[i].f);
tb = max(tb, tab[i].s);
//cout<<i<<" "<<tab[i].f<<" "<<tab[i].s<<'\n';
}
}
if(ta!=na||nb!=tb) solve(na-1, nb+1, ta, tb);
na = ta;
nb = tb;
}
long long minimum_walk(std::vector<int> p, int s) {
int n = p.size();
vector<int> odw(n);
long long wyn = 0;
vector<pair<int, int>> inp;
vector<pair<int, int>> inp2;
tab.resize(n, {-1, -1});
int globMax=-1e9, globMin=1e9;
for(int i = 0; i < n; i++){
int pt = i;
if(!odw[pt]){
if(p[pt]!=pt){
int mini = 1e9;
int maxi = -1e9;
vector<int> stck;
while(!odw[pt]){
stck.push_back(pt);
mini = min(mini, pt);
maxi = max(maxi, pt);
odw[pt] = true;
wyn+=abs(p[pt]-pt);
pt = p[pt];
}
globMax = max(globMax, maxi);
globMin = min(globMin, mini);
for(auto it:stck) tab[it] = {mini, maxi};
inp2.push_back({mini, -i});
inp2.push_back({maxi, i});
inp.push_back({mini, maxi});
}else{
tab[i] = {-1, -1};
odw[pt] = true;
}
}
}
inp.push_back({s, s});
sort(inp.begin(), inp.end());
int dal = -1;
int cA=-1, cB=-1;
bool bylo = false;
for(int i = 0; i < inp.size(); i++){
while(dal>inp[i].f){
dal = max(dal, inp[i].s);
i++;
if(i>=inp.size()) break;
}
if(dal>=s){
cB = dal;
bylo = true;
}
if(i<inp.size()){
if(i!=0) wyn+=2*(inp[i].f-dal);
dal = inp[i].s;
}
if(!bylo) cA=inp[i].f;
}
int pocz=s, kon=s;
//cout<<cA<<" "<<cB<<'\n';
while(true){
//cout<<pocz<<" "<<kon<<'\n';
solve(pocz, kon, pocz, kon);
//cout<<pocz<<" "<<kon<<'\n';
if(pocz>cA&&kon<cB){
wyn+=2;
pocz--;
kon++;
}else break;
}
return wyn;
}
Compilation message (stderr)
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < inp.size(); i++){
| ~~^~~~~~~~~~~~
books.cpp:78:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if(i>=inp.size()) break;
| ~^~~~~~~~~~~~
books.cpp:84:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | if(i<inp.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... |