Submission #1076290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076290		MilosMilutinovic	Inspections (NOI23_inspections)	C++14	100 / 100	296 ms	30380 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  vector<int> l(m), r(m);
  for (int i = 0; i < m; i++) {
    cin >> l[i] >> r[i];
  }
  set<array<long long, 3>> st;
  for (int i = 1; i <= n; i++) {
    // st.insert({i, i, -1 - i});
  }
  long long s = 0;
  vector<pair<long long, int>> ev;
  for (int i = 0; i < m; i++) {
    while (true) {
      auto it = st.lower_bound({l[i], -1, -1});
      if (it == st.end() || (*it)[1] > r[i]) {
        break;
      }
      array<long long, 3> v = *it;
      st.erase(it);
      if (v[1] < l[i]) {
        st.insert({l[i] - 1, v[1], v[2]});
      }
      if (v[0] > r[i]) {
        st.insert({v[0], r[i] + 1, v[2]});
      }
      int id = min(r[i], (int) v[0]);
      long long cur = s + id - l[i];
      long long bef = v[2] + id;
      ev.emplace_back(cur - bef - 1, min(r[i], (int) v[0]) - max(l[i], (int) v[1]) + 1);
    }
    st.insert({r[i], l[i], s - l[i]});
    s += r[i] - l[i] + 1;
  }
  /* for (auto& p : ev) {
    cout << p.first << " " << p.second << '\n';
  } */
  vector<long long> x(q);
  for (int i = 0; i < q; i++) {
    cin >> x[i];
  }
  sort(ev.rbegin(), ev.rend());
  vector<int> order(q);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return x[i] > x[j];
  });
  int ptr = 0;
  vector<long long> res(q);
  long long total = 0;
  for (int i : order) {
    while (ptr < (int) ev.size() && ev[ptr].first >= x[i]) {
      total += ev[ptr].second;
      ptr += 1;
    }
    res[i] = total;
  }
  for (int i = 0; i < q; i++) {
    cout << res[i] << " ";
  }
  return 0;
}

/*
5 3 7
1 3
3 5
2 3
0 1 2 3 4 5 6

6 6 7
1 6
1 5
1 4
1 3
1 2
1 1
1 2 3 4 5 6 7
*/

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 23 / 23