Submission #224226

#	Time	Username	Problem	Language	Result	Execution time	Memory
224226		bortoz	Pilot (NOI19_pilot)	C++17	89 / 100	1010 ms	60116 KiB

pilot

#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define fi first
#define se second

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int N, Q;
  cin >> N >> Q;

  vector<pair<int, int>> H(N);
  vector<int> Y(Q);

  for (int i = 0; i < N; i++) {
    cin >> H[i].fi;
    H[i].se = i;
  }
  for (int i = 0; i < Q; i++) {
    cin >> Y[i];
  }

  vector<bool> vis(N);
  vector<int> par(N), left(N), right(N);
  iota(par.begin(), par.end(), 0);
  iota(left.begin(), left.end(), 0);
  iota(right.begin(), right.end(), 1);

  function<ll(int)> way = [&](int v) {
    return 1ll * (right[v] - left[v]) * (right[v] - left[v] + 1) / 2;
  };

  function<int(int)> find = [&](int v) {
    return v == par[v] ? v : (par[v] = find(par[v]));
  };

  function<ll(int, int)> merge = [&](int a, int b) {
    a = find(a), b = find(b);
    ll r = way(a) + way(b);
    par[a] = b;
    left[b] = left[a];
    return way(b) - r;
  };

  ll sum = 0;
  vector<pair<int, ll>> res;

  sort(H.begin(), H.end());
  for (auto [h, x] : H) {
    vis[x] = true;
    if (x > 0 && vis[x - 1]) {
      sum += merge(x - 1, x);
    }
    if (x + 1 < N && vis[x + 1]) {
      sum += merge(x, x + 1);
    }
    res.emplace_back(h, sum += 1);
  }

  for (int i : Y) {
    auto it = upper_bound(res.begin(), res.end(), make_pair(i, (ll)1e18));
    cout << (it == res.begin() ? 0ll : prev(it)->se) << '\n';
  }

  return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 0 / 11