Submission #970874

#	Time	Username	Problem	Language	Result	Execution time	Memory
970874		nguyentunglam	Meetings (IOI18_meetings)	C++17	100 / 100	3099 ms	242376 KiB

meetings

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

const int N = 750'000 + 10;

int pre[N], nxt[N], lg[N], sp[20][N];

long long h[N];

vector<int> query[N];

struct IT {
pair<long long, long long> lazy[N << 2];

void gather(pair<long long, long long> &a, pair<long long, long long> &b) {
  if (b.first != -1e9) a = b;
  else a.second += b.second;
}

void push(int s, int l, int r) {
  if (l == r) return;
  gather(lazy[s << 1], lazy[s]);
  gather(lazy[s << 1 | 1], lazy[s]);
  lazy[s] = make_pair(-1e9, 0);
}

void up(int s, int l, int r, int from, int to, pair<long long, long long> val) {
  push(s, l, r);
  if (l > to || r < from) return;
  if (from <= l && r <= to) {
    gather(lazy[s], val);
    return;
  }
  int mid = l + r >> 1;
  up(s << 1, l, mid, from, to, val);
  up(s << 1 | 1, mid + 1, r, from, to, val);
}

pair<long long, long long> get(int s, int l, int r, int pos) {
  push(s, l, r);
  if (l == r) return lazy[s];
  int mid = l + r >> 1;
  if (pos <= mid) return get(s << 1, l, mid, pos);
  return get(s << 1 | 1, mid + 1, r, pos);
}
} prefix, suffix;

int best(int x, int y) {
  if (h[x] == h[y]) return x < y ? x : y;
  return h[x] > h[y] ? x : y;
}

int getmax (int l, int r) {
  int k = lg[r - l + 1];
  return best(sp[k][l], sp[k][r - (1 << k) + 1]);
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int q = L.size();
  int n = H.size();

  for(int i = 0; i < n; i++) sp[0][i] = i, h[i] = H[i];

  for(int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;

  for(int j = 1; j <= lg[n]; j++) for(int i = 0; i + (1 << j) - 1 < n; i++) {
    sp[j][i] = best(sp[j - 1][i], sp[j - 1][i + (1 << j - 1)]);
  }

  vector<long long> ans(q);

  for(int i = 0; i < q; i++) {
    ans[i] = 1e18;
//    cout << L[i] << " " << R[i] << " " << h[i] << endl;
    if (L[i] == R[i]) ans[i] = h[L[i]];
    else {
      int x = getmax(L[i], R[i]);
      query[x].emplace_back(i);
    }
  }

//  for(int i = 0; i < q; i++) cout << ans[i] << endl;

  vector<int> order(n);
  for(int i = 0; i < n; i++) order[i] = i;

  sort(order.begin(), order.end(), [] (const int &x, const int &y) {
       if (h[x] == h[y]) return x > y;
       return h[x] < h[y];
       });

  for(int i = 1; i <= 4 * n; i++) prefix.lazy[i] = suffix.lazy[i] = make_pair(-1e9, 0);

  auto get_prefix = [&] (int pos) {
    pair<long long, long long> tmp = prefix.get(1, 0, n - 1, pos);
    if (tmp.first == -1e9) return tmp.second;
    return tmp.first * pos + tmp.second;
  };

  auto get_suffix = [&] (int pos) {
    pair<long long, long long> tmp = suffix.get(1, 0, n - 1, pos);
    if (tmp.first == -1e9) return tmp.second;
    return tmp.first * pos + tmp.second;
  };

  for(int i = 0; i < n; i++) pre[i] = i - 1, nxt[i] = i + 1;

  for(int cur = 0; cur < n; cur++) {
    int v = order[cur];
    int from = pre[v], to = nxt[v];
    if (from >= 0) nxt[from] = to;
    if (to < n) pre[to] = from;
    from++; to--;

//    cout << from << " " << to << " " << v << endl;

    prefix.up(1, 0, n - 1, v, v, make_pair(0, get_prefix(v - 1) + h[v]));
    suffix.up(1, 0, n - 1, v, v, make_pair(0, get_suffix(v + 1) + h[v]));


    for(int &j : query[v]) {
//      cout << j << " " << v << endl;
      assert(from <= L[j]);
      assert(R[j] <= to);
      if (j == 0) {
//        cout << get_suffix(L[j]) + 1LL * (R[j] - v + 1) * h[v] << endl;
      }
      if (L[j] != v) ans[j] = min(ans[j], get_suffix(L[j]) + 1LL * (R[j] - v + 1) * h[v]);
      if (R[j] != v) ans[j] = min(ans[j], get_prefix(R[j]) + 1LL * (v - L[j] + 1) * h[v]);
    }

    long long left = get_prefix(v - 1);
    long long right = get_suffix(v + 1);

//    if (v == 2) cout << left << " " << right << endl;
//    cout << left << " " << right << endl;
//    cout << endl;

    int l, r, last;

    l = v + 1, r = to, last = v;

    while (l <= r) {
      int mid = l + r >> 1;
      if (left + h[v] * (mid - v + 1) <= h[v] * (v - from + 1)  + get_prefix(mid)) {
        last = mid;
        l = mid + 1;
      } else r = mid - 1;
    }

//    if (v == 2) cout << last << "@" << endl;

    if (v + 1 <= last) prefix.up(1, 0, n - 1, v + 1, last, make_pair(h[v], left - h[v] * (v - 1)));
    if (last + 1 <= to) prefix.up(1, 0, n - 1, last + 1, to, make_pair(-1e9, h[v] * (v - from + 1)));

    l = from, r = v - 1, last = v;

    while (l <= r) {
      int mid = l + r >> 1;
      if (right + h[v] * (v - mid + 1) <= h[v] * (to - v + 1) + get_suffix(mid)) {
        last = mid;
        r = mid - 1;
      } else l = mid + 1;
    }

    if (last <= v - 1) suffix.up(1, 0, n - 1, last, v - 1, make_pair(-h[v], right + h[v] * (v + 1)));
    if (from <= last - 1) suffix.up(1, 0, n - 1, from, last - 1, make_pair(-1e9, h[v] * (to - v + 1)));
    if (v == 2) {
//      cout << get_prefix(n - 1) << endl;
////      prefix.up(1, 0, n - 1, 0, 0, make_pair(0, 2));
//      cout << get_suffix(0) << endl;
//      cout << get_suffix(0) << endl;
//      cout << get_suffix(0) << endl;
    }
  }

  return ans;
}

#ifdef ngu
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
  int N = read_int();
  int Q = read_int();
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    H[i] = read_int();
  }
  std::vector<int> L(Q), R(Q);
  for (int j = 0; j < Q; ++j) {
    L[j] = read_int();
    R[j] = read_int();
  }

  std::vector<long long> C = minimum_costs(H, L, R);
  for (size_t j = 0; j < C.size(); ++j) {
    printf("%lld\n", C[j]);
  }
  return 0;
}
#endif // ngu

Compilation message (stderr)

meetings.cpp: In member function 'void IT::up(int, int, int, int, int, std::pair<long long int, long long int>)':
meetings.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid = l + r >> 1;
      |             ~~^~~
meetings.cpp: In member function 'std::pair<long long int, long long int> IT::get(int, int, int, int)':
meetings.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int mid = l + r >> 1;
      |             ~~^~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:69:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   69 |     sp[j][i] = best(sp[j - 1][i], sp[j - 1][i + (1 << j - 1)]);
      |                                                       ~~^~~
meetings.cpp:146:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |       int mid = l + r >> 1;
      |                 ~~^~~
meetings.cpp:161:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  161 |       int mid = l + r >> 1;
      |                 ~~^~~

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