Submission #909625

#	Time	Username	Problem	Language	Result	Execution time	Memory
909625		MilosMilutinovic	Employment (JOI16_employment)	C++14	100 / 100	192 ms	12280 KiB

employment

/**
 *    author:  wxhtzdy
 *    created: 10.09.2023 18:28:11
**/
#include <bits/stdc++.h>

using namespace std;

template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }                     
  vector<int> op(q);
  vector<int> x(q);
  vector<int> y(q);
  for (int i = 0; i < q; i++) {
    cin >> op[i];
    if (op[i] == 1) {
      cin >> x[i];
    } else {
      cin >> x[i] >> y[i];
      --x[i];
    }
  }
  vector<int> xs;
  for (int i = 0; i < n; i++) {
    xs.push_back(a[i]);
  }
  for (int i = 0; i < q; i++) {
    if (op[i] == 1) {
      xs.push_back(x[i]);
    } else {
      xs.push_back(y[i]);
    }
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  int sz = (int) xs.size();
  for (int i = 0; i < n; i++) {
    a[i] = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin());
  }
  for (int i = 0; i < q; i++) {
    if (op[i] == 1) {
      x[i] = (int) (lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin());
    } else {
      y[i] = (int) (lower_bound(xs.begin(), xs.end(), y[i]) - xs.begin());
    }
  }
  fenwick<int> f(sz);
  function<void(int, int)> Add = [&](int i, int x) {
    if (i < 0 || i >= n) {
      return;
    }
    f.modify(a[i], x);
    if (i > 0) {
      f.modify(min(a[i - 1], a[i]), -x);
    }
  };
  for (int i = 0; i < n; i++) {
    Add(i, +1);
  }
  for (int i = 0; i < q; i++) {
    if (op[i] == 1) {
      cout << f.get(sz - 1) - f.get(x[i] - 1) << '\n';
    } else {
      Add(x[i], -1);
      Add(x[i] + 1, -1);
      a[x[i]] = y[i];
      Add(x[i], +1);
      Add(x[i] + 1, +1);
    }
  }         
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60