Submission #1157978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157978		aeg	Pilot (NOI19_pilot)	C++20	100 / 100	386 ms	62184 KiB

pilot

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

#define int int64_t

int findval(int a) { return ((a * (a - 1)) / 2) + a; }

struct dsu {
  vector<int> vec;
  int ans = 0;
  dsu(int n) : vec(n, -1) {}
  int find(int n) {
    if (vec[n] < 0)
      return n;
    vec[n] = find(vec[n]);
    return vec[n];
  }
  void unify(int a, int b) {
    a = find(a), b = find(b);
    if (a == b)
      return;
    if (vec[a] > vec[b])
      swap(a, b);
    ans += findval((-1 * vec[a]) - vec[b]) - findval(-1 * vec[a]) - findval(-1 * vec[b]);
    vec[a] += vec[b];
    vec[b] = a;
  }
};

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  dsu a(n);
  vector<pair<int, int>> h(n);
  vector<int> hh(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i].first;
    h[i].second = i;
    hh[i] = h[i].first;
  }
  sort(h.begin(), h.end());
  vector<int> answers(q, -1);
  vector<pair<int, int>> qu(q);
  for (int i = 0; i < q; i++) {
    cin >> qu[i].first;
    qu[i].second = i;
  }
  sort(qu.begin(), qu.end());
  vector<bool> b(n, true);
  int ind = 0;
  for (int i = 0; i < q; i++) {
    while (ind < n && h[ind].first <= qu[i].first) {
      if (b[h[ind].second]) {
	a.ans ++;
	b[h[ind].second] = false;
      }
      if (h[ind].second > 0 && hh[h[ind].second - 1] <= h[ind].first) {
	if (b[h[ind].second - 1]) {
	    a.ans ++;
	    b[h[ind].second - 1] = false;
	}
        a.unify(h[ind].second, h[ind].second - 1);
      }
      if (h[ind].second < n - 1 && hh[h[ind].second + 1] <= h[ind].first) {
	if (b[h[ind].second + 1]) {
	    a.ans ++;
	    b[h[ind].second + 1] = false;
	}
        a.unify(h[ind].second, h[ind].second + 1);
      }
      ind++;
    }
    answers[qu[i].second] = a.ans;
  }
  copy(answers.begin(), answers.end(), ostream_iterator<int>(cout, "\n"));
}

• 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: 11 / 11