Submission #987159

#	Time	Username	Problem	Language	Result	Execution time	Memory
987159		AdamGS	Ancient Books (IOI17_books)	C++17	22 / 100	599 ms	118364 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 int LIM=1e6+7;
ll F[LIM], mi[LIM], ma[LIM];
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 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;
  rep(i, n) if(fnd(i)==i) V.pb({{ma[i]-mi[i], i}, {mi[i], ma[i]}});
  sort(all(V));
  for(auto i : V) {
    while(true) {
      auto it=S.lower_bound(i.nd.st);
      if(it==S.end()) break;
      auto a=*it;
      if(a>i.nd.nd) break;
      S.erase(a);
      uni(i.st.nd, a);
    }
  }
  while(n>0 && p[n-1]==n-1) --n;
  ll ans=0;
  rep(i, n) ans+=abs(p[i]-i);
  ll akt=ma[fnd(s)]+1;
  while(akt<n) {
    ans+=2;
    akt=ma[fnd(akt)]+1;
  }
  return ans;
}

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