Submission #1038911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038911		huutuan	Meetings (IOI18_meetings)	C++14	60 / 100	1120 ms	508172 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e6+10, LG=20;
int pf[5010][5010], n, a[N], q, l[N][20], r[N][20];
pair<int, int> st[LG][N];

vector<long long> minimum_costs(vector<int32_t> H, vector<int32_t> L,
                                vector<int32_t> R) {
   n=H.size(), q=L.size();
   for (auto &i:L) ++i;
   for (auto &i:R) ++i;
   for (int i=1; i<=n; ++i) a[i]=H[i-1];
   vector<int> res;
   if (n<=5000 && q<=5000){
      for (int i=1; i<=n; ++i){
         for (int j=i, mx=0; j<=n; ++j){
            mx=max(mx, a[j]);
            pf[i][j]=mx;
         }
         for (int j=i, mx=0; j>=1; --j){
            mx=max(mx, a[j]);
            pf[i][j]=mx;
         }
         partial_sum(pf[i], pf[i]+n+1, pf[i]);
      }
      for (int i=0; i<q; ++i){
         int ans=1e18;
         for (int j=L[i]; j<=R[i]; ++j) ans=min(ans, pf[j][R[i]]-pf[j][L[i]-1]);
         res.push_back(ans);
      }
      return res;
   }
   for (int i=1; i<=n; ++i){
      for (int j=0; j<20; ++j){
         if (a[i]>j) l[i][j]=i+1;
         else l[i][j]=i==1?1:l[i-1][j];
      }
   }
   for (int i=n; i>=1; --i){
      for (int j=0; j<20; ++j){
         if (a[i]>j) r[i][j]=i-1;
         else r[i][j]=i==n?n:r[i+1][j];
      }
   }
   for (int i=1; i<=n; ++i){
      st[0][i].second=i;
      for (int j=0; j<20; ++j){
         st[0][i].first+=max(0ll, r[i][j]-l[i][j]+1);
      }
   }
   for (int i=1; i<LG; ++i) for (int j=1; j+(1<<i)-1<=n; ++j){
      st[i][j]=max(st[i-1][j], st[i-1][j+(1<<(i-1))]);
   }
   auto get=[&](int ll, int rr) -> int {
      int lg=__lg(rr-ll+1);
      return max(st[lg][ll], st[lg][rr-(1<<lg)+1]).second;
   };
   for (int i=0; i<q; ++i){
      vector<int> v;
      v.push_back(L[i]-1);
      v.push_back(R[i]);
      for (int j=0; j<20; ++j) v.push_back(max(min(r[L[i]][j], (int)R[i]), (int)L[i]-1));
      for (int j=0; j<20; ++j) v.push_back(max(min(l[R[i]][j]-1, (int)R[i]), (int)L[i]-1));
      sort(v.begin(), v.end());
      vector<int> id;
      for (int j=1; j<(int)v.size(); ++j) if (v[j]!=v[j-1]) id.push_back(get(v[j-1]+1, v[j]));
      int ans=20*(R[i]-L[i]+1);
      for (int j:id){
         int cur=20*(R[i]-L[i]+1);
         for (int k=0; k<20; ++k) cur-=max(0ll, min(r[j][k], (int)R[i])-max(l[j][k], (int)L[i])+1);
         ans=min(ans, cur);
      }
      res.push_back(ans);
   }
   return res;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 40