Submission #421925

#	Time	Username	Problem	Language	Result	Execution time	Memory
421925		Hegdahl	Meetings (IOI18_meetings)	C++17	0 / 100	1563 ms	3268 KiB

meetings

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;
using ll = long long;

const ll INF = 1LL<<60;

const int mxN = 75e4;
const int offset = 2<<__lg(mxN-1);

int n, q;
vector<int> h;

ll val[2*offset];

void upd(int i, ll x) {
  i += offset;
  val[i] += x;
  while (i /= 2) val[i] = min(val[2*i], val[2*i+1]);
}

ll qry(int i, int j) {
  i += offset-1;
  j += offset+1;
  ll ans = INF;
  while (i+1 < j) {
    if (i%2 == 0) ans = min(ans, val[i+1]);
    if (j%2 == 1) ans = min(ans, val[j-1]);
    i /= 2, j /= 2;
  }
  return ans;
}

void insert(int i) {
  for (int j = i, mx = h[i]; j < n; ++j) {
    mx = max(mx, h[j]);
    upd(j, mx);
  }
  for (int j = i-1, mx = h[i]; j >= 0; --j) {
    mx = max(mx, h[j]);
    upd(j, mx);
  }
}

void erase(int i) {
  for (int j = i, mx = 0; j < n; ++j) {
    mx = max(mx, h[j]);
    upd(j, -mx);
  }
  for (int j = i-1, mx = 0; j >= 0; --j) {
    mx = max(mx, h[j]);
    upd(j, -mx);
  }
}

ll solve(int L, int R) {
  static int CL = 0, CR = -1;
  while (CR < R) insert(++CR);
  while (CL > L) insert(--CL);
  while (CR > R) erase(CR--);
  while (CL < L) erase(CL++);
  return qry(L, R);
}

vector<ll> minimum_costs(vector<int> h_, vector<int> l, vector<int> r) {
  h = h_;
  n = (int)h.size();
  q = (int)l.size();
  vector<ll> ans(q);

  const int R = sqrt(n)+1;

  vector<int> s(q);
  iota(s.begin(), s.end(), 0);
  sort(s.begin(), s.end(), [&](int i, int j) -> bool {
    if (l[i]/R != l[j]/R) return l[i]/R < l[j]/R;
    return (r[i]>r[j])^l[i];
  });

  for (int qq : s)
    ans[qq] = solve(l[qq], r[qq]);

  return ans;
}

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