Submission #1067251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067251		juicy	Employment (JOI16_employment)	C++17	100 / 100	524 ms	25500 KiB

employment

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;

using namespace __gnu_pbds;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

template<class T>
using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

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

  int n, m; cin >> n >> m;
  vector<int> a(n);
  array<Tree<int>, 2> st;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    st[0].insert(a[i]);
    if (i) {
      st[1].insert(min(a[i], a[i - 1]));
    }
  }
  auto ers = [&](int i) {
    st[0].erase(st[0].upper_bound(a[i]));
    if (i) {
      st[1].erase(st[1].upper_bound(min(a[i], a[i - 1])));
    }
    if (i + 1 < n) {
      st[1].erase(st[1].upper_bound(min(a[i], a[i + 1])));
    }
  };
  auto ins = [&](int i, int x) {
    a[i] = x;
    st[0].insert(a[i]);
    if (i) {
      st[1].insert(min(a[i], a[i - 1]));
    }
    if (i + 1 < n) {
      st[1].insert(min(a[i], a[i + 1]));
    }
  };
  auto count = [&](Tree<int> &st, int x) {
    return st.size() - st.order_of_key(x);
  };
  auto qry = [&](int x) {
    return count(st[0], x) - count(st[1], x);
  };
  while (m--) {
    int t; cin >> t;
    if (t == 1) {
      int b; cin >> b;
      cout << qry(b) << "\n";
    } else {
      int c, d; cin >> c >> d; --c;
      ers(c);
      ins(c, d);
    }
  }
  return 0;
}

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