제출 #966952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966952		stefanneagu	Pilot (NOI19_pilot)	C++17	89 / 100	44 ms	14676 KiB

pilot

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5 + 1;

struct str {
  int aa, i;
} a[nmax], ord[nmax];

int v[nmax], ans[nmax], sz[nmax], root[nmax];

bool f[nmax];

int cmp(str x, str y) {
  return x.aa < y.aa;
}

int find(int a) {
  if(root[a] == a) {
    return a;
  }
  return root[a] = find(root[a]);
}

int curr = 0;

void unite(int a, int b) {
  if(a == b) {
    cout << a << " " << b << '\n';
    exit(0);
    // assert(0); // nu cred ca ar tb sa aj aici
  }
  if(sz[a] < sz[b]) {
    swap(a, b);
  }
  curr += sz[a] * sz[b];
  // cout << "+ " << sz[a] << " " << sz[b] << '\n';
  root[b] = a;
  sz[a] += sz[b];
}

void upd(int a) {
  f[a] = 1;
  curr++;
  if(f[a - 1] == 1) {
    // cout << "? " << a << " " << a - 1 << '\n';
    unite(find(a), find(a - 1));
  }
  if(f[a + 1] == 1) {
    // cout << "! " << a << " " << a + 1 << '\n';
    unite(find(a), find(a + 1));
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  cout.tie();
  int n, q;
  cin >> n >> q;
  for(int i = 1; i <= n; i++) {
    sz[i] = 1, root[i] = i;
    cin >> v[i];
    ord[i].aa = v[i];
    ord[i].i = i;
  }
  sort(ord + 1, ord + n + 1, cmp);
  for(int i = 1; i <= q; i++) {
    cin >> a[i].aa;
    a[i].i = i;
  }
  sort(a + 1, a + q + 1, cmp);
  int j = 1;
  for(int i = 1; i <= q; i++) { // rainboy orz
    while(j <= n && ord[j].aa <= a[i].aa) {
      // cout << "~ " << ord[j].i << "\n";
      upd(ord[j].i);
      j++;
    }
    ans[a[i].i] = curr;
    // cout << '\n';
  }
  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: 0 / 11