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"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int boss[1000005],mx[1000005],mi[1000005];
int finds(int x)
{
if(boss[x]==x) return x;
return boss[x]=finds(boss[x]);
}
void Union(int a,int b)
{
a=finds(a),b=finds(b);
boss[a]=b,mx[b]=max(mx[b],mx[a]),mi[b]=min(mi[b],mi[a]);
}
long long minimum_walk(vector<int> p, int s)
{
ll ans=0,ls=0;
for(int i=0;i<p.size();++i) boss[i]=i,mx[i]=i,mi[i]=i;
for(int i=0;i<p.size();++i)
Union(i,p[i]);
for(int i=0;i<p.size();++i)
ans+=abs(p[i]-i);
for(int i=0;i<p.size();)
if(finds(i),mx[boss[i]]==mi[boss[i]]) ++i;
else
if(mi[boss[i]]<=ls) ls=mx[boss[i]],i=mx[boss[i]]+1;
else ans+=(mi[boss[i]]-ls)*2,ls=mx[boss[i]],i=mx[boss[i]]+1;
return ans;
}
Compilation message (stderr)
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();++i) boss[i]=i,mx[i]=i,mi[i]=i;
~^~~~~~~~~
books.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();++i)
~^~~~~~~~~
books.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();++i)
~^~~~~~~~~
books.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.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... |