Submission #1035240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035240		NeroZein	Meetings (IOI18_meetings)	C++17	19 / 100	5526 ms	13648 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> h, ql, qr;

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  int n = (int) H.size();
  int q = (int) L.size();
  h = H; ql = L, qr = R;
  
  const int LOG = 32 - __builtin_clz(n);
  vector<vector<int>> spa(LOG); 
  spa[0] = h;
  for (int j = 1; j < LOG; ++j) {
    spa[j].resize(n - (1 << j) + 1); 
    for (int i = 0; i + (1 << j) <= n; ++i) {
      spa[j][i] = max(spa[j - 1][i], spa[j - 1][i + (1 << (j - 1))]);
    }
  }
  auto get_max = [&](int l, int r) {
    int lg = 31 - __builtin_clz(r - l + 1); 
    return max(spa[lg][l], spa[lg][r - (1 << lg) + 1]);
  };
  
  vector<long long> ret(q);
  for (int qind = 0; qind < q; ++qind) {
    vector<long long> change(n); 
    int l = ql[qind], r = qr[qind];
    for (int i = l; i < r; ++i) {
      if (h[i] < h[i + 1]) {//there's a suffix that will get affected (increase)
        int cur = i;
        int mx = h[cur];
        while (cur >= l && mx < h[i + 1]) {
          int lo = l, hi = cur; 
          while (lo < hi) {
            int mid = (lo + hi) / 2; 
            if (get_max(mid, cur) == mx) {
              hi = mid;
            } else {
              lo = mid + 1; 
            }
          }
          change[i] += (long long) (cur - lo + 1) * (h[i + 1] - mx); 
          if (lo > l) {
            cur = lo - 1; 
            mx = h[lo - 1];            
          } else {
            break; 
          }
        }
      } 
      else if (h[i] > h[i + 1]) {
        int cur = i + 1;
        int mx = h[cur];
        while (cur <= r && mx < h[i]) {
          int lo = cur, hi = r;
          while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (get_max(cur, mid) == mx) {
              lo = mid;
            } else {
              hi = mid - 1; 
            }
          }
          change[i] -= (long long) (hi - cur + 1) * (h[i] - mx); 
          if (hi < r) {
            cur = hi + 1;
            mx = h[hi + 1];             
          } else {
            break; 
          }
        }
      }
    }
    long long init_cost = 0; 
    int cur = l;
    int mx = h[cur]; 
    while (cur <= r) {
      int lo = cur, hi = r; 
      while (lo < hi) {
        int mid = (lo + hi + 1) / 2; 
        if (get_max(cur, mid) == mx) {
          lo = mid;
        } else {
          hi = mid - 1;
        }
      }
      init_cost += (long long) (hi - cur + 1) * mx;
      if (hi < r) {
        cur = hi + 1; 
        mx = h[hi + 1];        
      } else {
        break; 
      }
    }
    long long mn = init_cost;
    for (int i = l; i < r; ++i) {
      init_cost += change[i];
      mn = min(mn, init_cost); 
    }
    ret[qind] = mn; 
  }
  return ret; 
}

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