oj.uz

Submission #1037092

# Submission time Handle Problem Language Result Execution time Memory
1037092 2024-07-28T04:03:25 Z huutuan Ancient Books (IOI17_books) C++14
0 / 100
 700 ms 1048576 KB 
#include "books.h"

#include <bits/stdc++.h>

using namespace std;

const int N=1e6, LG=20;
int tl, tr;
int vis[N], n, stmin[LG][N], stmax[LG][N];
pair<int, int> ll[N], rr[N];
int check[N];
long long ans=0;

int getmin(int l, int r){
   int lg=__lg(r-l+1);
   return min(stmin[lg][l], stmin[lg][r-(1<<lg)+1]);
}

int getmax(int l, int r){
   int lg=__lg(r-l+1);
   return max(stmax[lg][l], stmax[lg][r-(1<<lg)+1]);
}

void extend(int &l, int &r){
   while (1){
      int nl=getmin(l, r), nr=getmax(l, r);
      if (nl==l && nr==r) break;
      l=nl; r=nr;
   }
}

void dp(int l, int r){
   extend(l, r);
   if (l==tl && r==tr) return;
   int l1=tl, r1=r, l2=l, r2=tr;
   if (ll[l].first || ll[l].second){
      l1=ll[l].first;
   }
   if (rr[r].first || rr[r].second){
      r2=rr[r].second;
   }
   int c1=check[l]-check[l1];
   int c2=check[r2]-check[r];
   if (l1==l) c1=1e9;
   if (r2==r) c2=1e9;
   ans+=min(c1, c2)*2;
   return dp(l1, r1);
}

long long minimum_walk(vector<int> p, int s) {
   n=p.size();
   for (int i=0; i<n; ++i) if (!vis[i]){
      vector<int> cc;
      int u=i;
      stmin[0][i]=i; stmax[0][i]=i;
      int maxl=-1, minr=-1;
      while (!vis[u]){
         if (u<s){
            if (maxl==-1 || maxl<u) maxl=u;
         }
         if (u>s){
            if (minr==-1 || minr>u) minr=u;
         }
         vis[u]=1;
         cc.push_back(u);
         stmin[0][i]=min(stmin[0][i], u);
         stmax[0][i]=max(stmax[0][i], u);
         ans+=abs(u-p[u]);
         u=p[u];
      }
      if (stmin[0][i]<s && s<stmax[0][i]){
         ll[maxl+1]=rr[minr-1]={maxl, minr};
      }else{
         int l=stmin[0][i], r=stmax[0][i];
         ++check[l]; --check[r];
      }
      for (int j:cc) stmin[0][j]=stmin[0][i], stmax[0][j]=stmax[0][i];
   }
   partial_sum(check, check+n, check);
   for (int i=n-1; i>0; --i) check[i]=!check[i-1];
   check[0]=0;
   partial_sum(check, check+n, check);
   for (int i=1; i<=s; ++i){
      if (ll[i].first==0 && ll[i].second==0) ll[i]=ll[i-1];
   }
   for (int i=n-2; i>=s; --i){
      if (rr[i].first==0 && rr[i].second==0) rr[i]=rr[i+1];
   }
   for (int i=1; i<LG; ++i) for (int j=0; j+(1<<i)-1<n; ++j){
      stmin[i][j]=min(stmin[i-1][j], stmin[i-1][j+(1<<(i-1))]);
      stmax[i][j]=max(stmax[i-1][j], stmax[i-1][j+(1<<(i-1))]);
   }
   tl=0, tr=n-1;
   while (tl<s && stmin[0][tl]==tl && stmax[0][tl]==tl) ++tl;
   while (tr>s && stmin[0][tr]==tr && stmax[0][tr]==tr) --tr;
   dp(s, s);
   return ans;
}

Compilation message

books.cpp: In function 'void dp(int, int)':
books.cpp:35:21: warning: unused variable 'l2' [-Wunused-variable]
   35 |    int l1=tl, r1=r, l2=l, r2=tr;
      |                     ^~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 687 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 687 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 687 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 47448 KB Output is correct
2 Correct 4 ms 47448 KB Output is correct
3 Correct 4 ms 47620 KB Output is correct
4 Runtime error 700 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 687 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -