Submission #1237324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237324		mychecksedad	모임들 (IOI18_meetings)	C++20	0 / 100	30 ms	18112 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ll long long int
#define pii pair<int,int>
const int N = 1e5+100, M = 5010, K = 22;
 
int rmq[N][K], dp[N][K], pd[N][K], lp[N][K], rp[N][K], rmq2[N][K];
ll pref[M][M];
ll h[N];
int rmq3[21][N][19];
int get(int l, int r){
  int k = __lg(r-l+1);
  return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
int get3(int l, int r, int d){
  int k = __lg(r-l+1);
  return min(rmq3[d][l][k], rmq3[d][r-(1<<k)+1][k]);
}
int get2(int l, int r){
  int k = __lg(r-l+1);
  int lx = rmq2[l][k];
  int rx = rmq2[r-(1<<k)+1][k];
  return h[lx] >= h[rx] ? lx : rx;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
  int n = H.size();
  int q = L.size();
  for(int i = 0; i < n; ++i) rmq[i+1][0] = H[i];
  for(int i = 1; i <= n; ++i){
    h[i] = H[i-1];
  }
  for(int i = 0; i < n; ++i) rmq2[i+1][0] = i;
  for(int j = 1; j < K; ++j){
    for(int i = 1; i + (1<<j) <= n + 1; ++i){
      rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
      int lx = rmq2[i][j-1];
      int rx = rmq2[i+(1<<(j-1))][j-1];
      if(H[lx-1] >= H[rx-1]) rmq2[i][j] = lx;
      else rmq2[i][j] = rx;
    }
  }
  // for(int i = 1; i <= n; ++i){
  //   pref[i][0] = 0;
  //   for(int j = 1; j <= n; ++j) pref[i][j] = pref[i][j - 1] + (i <= j ? get(i, j) : get(j, i));
  // }
  for(int i = 0; i < q; ++i) L[i]++, R[i]++;
  vector<ll> C;
  // if(n <= 5000 && q <= 5000){
  //   for(int _ = 0; _ < q; ++_){
  //     ll ans = 1e18;
  //     for(int i = L[_]; i <= R[_]; ++i){
  //       ll cur = pref[i][R[_]] - pref[i][L[_] - 1];
  //       // for(int j = L[_]; j <= R[_]; ++j){
  //       //   if(i<=j) cur += get(i, j);
  //       //   else cur += get(j,i);
  //       // } 
  //       ans=min(ans,cur);
  //     }
  //     C.pb(ans);
  //   }
  //   return C;
  // }
  for(int d = 1; d <= 20; ++d){
    dp[0][d] = 0;
    int j = 0, j2 = 0;
    for(int i = 1; i <= n; ++i){
      if(h[i] > d){
        lp[i][d] = i + 1;
        dp[i][d] = 0;
        j2 = i;
        j = i;
      }else if(h[i] == d){
        if(i == 1 || h[i-1] > d){
          dp[i][d] = d;
        }else{
          dp[i][d] = min((lp[i-1][d]-j2)*d + d + dp[i-1][d-1], (i-j)*d + dp[j][d]); // takes it all
        }
        j = i;
        lp[i][d] = i;
      }else{
        lp[i][d] = j;
        dp[i][d] = min(j == 0 ? i * d : dp[j-1][d] + d*(i-j+1), dp[i][d-1] + dp[j][d]);
      }
      // cerr << dp[i][d] << ' ';
    }
    // cerr << '\n';
  }
  for(int d = 1; d <= 20; ++d){
    pd[n + 1][d] = 0;
    int j = n + 1, j2 = n+1;
    for(int i = n; i >= 1; --i){
      if(h[i] > d){
        rp[i][d] = i - 1;
        pd[i][d] = 0;
        j2 = i;
        j = i;
      }else if(h[i] == d){
        if(i == n || h[i + 1] > d){
          pd[i][d] = d;
        }else{
          pd[i][d] = min((j2-rp[i+1][d])*d + d + pd[i+1][d-1], (j-i)*d + pd[j][d]);
        }
        rp[i][d] = i;
        j = i;
      }else{
        rp[i][d] = j;
        pd[i][d] = min(j == n+1 ? (n-i+1) * d : pd[j+1][d] + d*(j-i+1), pd[i][d-1] + pd[j][d]);
      }
      // cerr << pd[i][d] << ' ' << rp[i][d] << '\n';
    }
    // cerr << '\n';
  }
  for(int d = 1; d <= 20; ++d){
    for(int j = 1; j <= n; ++j){
      rmq3[d][j][0] = 1e9;
      if(h[j] >= d) rmq3[d][j][0] = dp[j-1][d-1] - (j-1-lp[j-1][d]) * d;
    }
    for(int j = 1; j < 19; ++j){
      for(int i = 1; i + (1<<j) <= n+1; ++i){
        rmq3[d][i][j] = min(rmq3[d][i][j-1], rmq3[d][i+(1<<(j-1))][j-1]);
      }
    }
  }
  for(int j = 0; j < q; ++j){
    int ans = 1e9;
    int l = L[j], r = R[j];
    int mx = get(l, r);
    if(mx==1){
      C.pb(r-l+1);
      continue;
    }
    ans = min({mx * (r-l+1), pd[l][mx-1] + (r-rp[l][mx]+1) * mx, dp[r][mx-1] + (lp[r][mx]-l+1) * mx});
    int cnt = 0;
    int lpt = get2(l, r);
    if(lpt < r)
      ans = min(ans, (r-l+1)*mx + get3(lpt + 1, r, mx));
    // for(int i = l; i <= r; ++i){
    //   if(h[i] == mx){
    //     ++cnt;
    //     if(cnt > 1 && i > l){
    //       ans = min(ans, dp[i-1][mx-1] + (r-i+1 + lp[i-1][mx]-l+1)*mx);
    //     }
    //   }
    // }
    C.pb(ans);
  }
  return C;
}

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