Submission #1036250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036250		ind1v	Pilot (NOI19_pilot)	C++11	100 / 100	429 ms	53328 KiB

pilot

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

struct dsu {
  int lab[N];
  int cnt[N];
  bool on[N];
  long long cur;
  
  dsu() {
    memset(lab, -1, sizeof(lab));
    fill(cnt, cnt + N, 1);
    cur = 0;
  }
  
  int find(int u) {
    return lab[u] < 0 ? u : lab[u] = find(lab[u]);
  }
  
  bool merge(int u, int v) {
    if ((u = find(u)) == (v = find(v))) {
      return false;
    }
    if (lab[u] > lab[v]) {
      swap(u, v);
    }
    lab[u] += lab[v];
    lab[v] = u;
    cur -= 1LL * cnt[u] * (cnt[u] + 1) / 2;
    cur -= 1LL * cnt[v] * (cnt[v] + 1) / 2;
    cnt[u] += cnt[v];
    cur += 1LL * cnt[u] * (cnt[u] + 1) / 2;
    return true;
  }
};

int n, q;
int h[N], y[N];
int ord_h[N], ord_y[N];
long long ans[N];
dsu g;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
  }
  for (int i = 1; i <= q; i++) {
    cin >> y[i];
  }
  iota(ord_h + 1, ord_h + n + 1, 1);
  sort(ord_h + 1, ord_h + n + 1, [](int u, int v) -> bool {
    return h[u] < h[v];
  });
  iota(ord_y + 1, ord_y + q + 1, 1);
  sort(ord_y + 1, ord_y + q + 1, [](int u, int v) -> bool {
    return y[u] < y[v];
  });
  for (int i = 1, j = 1; i <= q; i++) {
    while (j <= n && h[ord_h[j]] <= y[ord_y[i]]) {
      g.on[ord_h[j]] = true;
      g.cur++;
      if (ord_h[j] - 1 >= 1 && g.on[ord_h[j] - 1]) {
        g.merge(ord_h[j], ord_h[j] - 1);
      }
      if (ord_h[j] + 1 <= n && g.on[ord_h[j] + 1]) {
        g.merge(ord_h[j], ord_h[j] + 1);
      }
      j++;
    }
    ans[ord_y[i]] = g.cur;
  }
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << '\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: 11 / 11