제출 #1280873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280873		aeg	Inspections (NOI23_inspections)	C++20	100 / 100	665 ms	35720 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int int64_t

struct inter {
  int l, r;
  long long t;
  inter(int l = 0, int r = 0, long long t = 0) : l(l), r(r), t(t) {}
};

bool operator<(inter const &a, inter const &b) {
  if (a.l != b.l)
    return a.l < b.l;
  else if (a.r != b.r)
    return a.r < b.r;
  else
    return a.t < b.t;
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m, q;
  cin >> n >> m >> q;
  set<inter> s;
  map<long long, long long> mp;
  s.insert(inter(1, n, INT64_MIN));

  int curt = 0;

  for (int _ = 0; _ < m; _++) {
    int l, r;
    cin >> l >> r;
    auto it = s.lower_bound(inter(l - 1, INT_MAX, INT64_MAX));
    vector<inter> tomod;
    if (it->l != l)
      it--;
    while (it != s.end() && it->l <= r) {
      tomod.push_back(*it);
      it++;
    }
    for (int i = 1; i < tomod.size() - 1; i++) {
      s.erase(tomod[i]);
      if (tomod[i].t < 0)
        continue;

      mp[(int64_t)(tomod[i].l) - (int64_t)(l) + curt - tomod[i].t] +=
          tomod[i].r - tomod[i].l + 1;
    }

    if (tomod.size() == 1) {
      if (tomod[0].t >= 0)
        mp[curt - (int64_t)((int64_t)(tomod[0].t) + (int64_t)(l) -
                            (int64_t)(tomod[0].l))] += r - l + 1;

      s.erase(tomod[0]);
      if (l != tomod[0].l)
        s.insert(inter(tomod[0].l, l - 1, tomod[0].t));
      if (r != tomod[0].r)
        s.insert(inter(r + 1, tomod[0].r, tomod[0].t + r + 1 - tomod[0].l));
    } else {
      if (tomod[0].t >= 0)
        mp[curt - (int64_t)((int64_t)(tomod[0].t) + (int64_t)(l) -
                            (int64_t)(tomod[0].l))] += tomod[0].r - l + 1;
      s.erase(tomod[0]);
      if (l != tomod[0].l)
        s.insert(inter(tomod[0].l, l - 1, tomod[0].t));

      if (tomod.back().t >= 0)
        mp[(int64_t)(tomod.back().l) - (int64_t)(l) + curt - tomod.back().t] +=
            r - tomod.back().l + 1;
      s.erase(tomod.back());
      if (r != tomod.back().r)
        s.insert(inter(r + 1, tomod.back().r,
                       tomod.back().t + r + 1 - tomod.back().l));
    }

    s.insert(inter(l, r, curt));

    curt += r - l + 1;
  }

  vector<pair<long long, long long>> suf;
  if (mp.begin()->first != 1)
    suf.push_back({0, 0});
  for (auto &[x, y] : mp) {
    suf.push_back({x - 1, y});
  }

  for (int i = suf.size() - 1; i > 0; i--)
    suf[i - 1].second += suf[i].second;

  while (q--) {
    int tmp;
    cin >> tmp;
    int ind = lower_bound(suf.begin(), suf.end(),
                          pair<long long, long long>{tmp, 0}) -
              suf.begin();

    if (ind == suf.size())
      cout << "0 ";
    else {
      cout << suf[ind].second << ' ';
    }
  }
  cout << '\n';
}

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