Submission #826242

#	Time	Username	Problem	Language	Result	Execution time	Memory
826242		Sohsoh84	Ancient Books (IOI17_books)	C++17	70 / 100	2072 ms	252228 KiB

books

#include<bits/stdc++.h>
#include "books.h"
#define X first
#define Y second
using namespace std;

typedef pair<int,int> pii;
const int maxn=2e6,inf=1e9;
long long ans;
int n,cnt,MIN[maxn],MAX[maxn],nex[maxn],mol[maxn],nl,nr,x,y;
bool mark[maxn],seg[maxn];
map<pii,int> dp;
pii P[maxn];
vector<int>vec;

void dfs(int v,int u)
{
  mark[v]=true;
  mol[v]=cnt;
  MIN[cnt]=min(MIN[cnt],v),MAX[cnt]=max(MAX[cnt],v);
  if(nex[v]!=u) dfs(nex[v],u);
}

int go(int l,int r)
{
  if(l==0 && r==n-1) return 0;
  if(dp[pii(l,r)]) return dp[pii(l,r)];
  return dp[pii(l,r)]=min((l==0?inf:go(P[mol[l-1]].X,max(P[mol[l-1]].Y,r))),(r==n-1?inf:go(min(l,P[mol[r+1]].X),P[mol[r+1]].Y)))+2;
}

void ok(int k)
{
  if(!seg[k])
    nl=min(nl,MIN[k]),nr=max(nr,MAX[k]),vec.push_back(k);
  else
    nl=min(nl,P[k].X),x=min(x,P[k].X),nr=max(nr,P[k].Y),y=max(y,P[k].Y);
}

void fmol(int k)
{
  x=y=MIN[k];
  vec.clear();vec.push_back(k);
  nl=MIN[k],nr=MAX[k];
  while(nl<x || y<nr)
    {
      if(nl<x) x--,ok(mol[x]);
      else y++,ok(mol[y]);
    }
  for(int i=0;i<vec.size();i++)
    P[vec[i]]=pii(x,y),seg[vec[i]]=true;
}

long long minimum_walk(vector<int> p, int s)
{
  n=p.size();
  for(int i=0;i<n;i++) nex[i]=p[i];
  for(int i=0;i<n;i++)
    {
      ans+=abs(i-p[i]);
      if(!mark[i]) {
	MIN[cnt]=MAX[cnt]=i;
	dfs(i,i);
	cnt++;
      }
    }
  if(ans==0) return 0;
  for(int i=0;p[i]==i && i<s;i++)
    ans-=2;
  for(int i=n-1;p[i]==i && i>s;i--)
    ans-=2;
  for(int i=cnt-1;i>-1;i--)
    if(!seg[i])
      fmol(i);
  ans+=go(P[mol[s]].X,P[mol[s]].Y);
  return ans;
}

Compilation message (stderr)

books.cpp: In function 'void fmol(int)':
books.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i=0;i<vec.size();i++)
      |               ~^~~~~~~~~~~

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