Submission #987163

#	Time	Username	Problem	Language	Result	Execution time	Memory
987163		AdamGS	Ancient Books (IOI17_books)	C++17	50 / 100	463 ms	85704 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e9+7;
const int LIM=1e6+7;
ll F[LIM], mi[LIM], ma[LIM], l, r;
set<ll>S;
ll fnd(ll x) {
  if(F[x]==x) return x;
  return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
  if(fnd(a)==fnd(b)) return;
  ma[fnd(a)]=max(ma[fnd(a)], ma[fnd(b)]);
  mi[fnd(a)]=min(mi[fnd(a)], mi[fnd(b)]);
  F[fnd(b)]=fnd(a);
}
ll solve(ll aktl, ll aktr, ll aktmi, ll aktma) {
  if(aktl>aktmi) {
    --aktl;
    aktmi=min(aktmi, mi[fnd(aktl)]);
    aktma=max(aktma, ma[fnd(aktr)]);
    return solve(aktl, aktr, aktmi, aktma);
  }
  if(aktr<aktma) {
    ++aktr;
    aktmi=min(aktmi, mi[fnd(aktr)]);
    aktma=max(aktma, ma[fnd(aktr)]);
    return solve(aktl, aktr, aktmi, aktma);
  }
  if(aktl==l && aktr==r) return 0;
  ++aktr;
  aktmi=min(aktmi, mi[fnd(aktr)]);
  aktma=max(aktma, ma[fnd(aktr)]);
  return solve(aktl, aktr, aktmi, aktma)+2;
}
ll minimum_walk(vector<int>p, int s) {
  ll n=p.size();
  rep(i, n) {
    F[i]=ma[i]=mi[i]=i;
    S.insert(i);
  }
  rep(i, n) uni(i, p[i]);
  vector<pair<pair<ll,ll>,pair<ll,ll>>>V;
  l=0; r=n-1;
  while(l<s && p[l]==l) ++l;
  while(r>s && p[r]==r) --r;
  ll ans=0;
  rep(i, n) ans+=abs(p[i]-i);
  return ans+solve(s, s, mi[fnd(s)], ma[fnd(s)]);
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30