Submission #1133412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133412		duckindog	Inspections (NOI23_inspections)	C++17	77 / 100	796 ms	105920 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 200'000 + 10,
          MAX = 50'000'000'000;
int n, m, q;
int a[N];

namespace IT { 
  struct Node { 
    int l, r, value;
    Node() : l(0), r(0), value(0) {}
    Node(int l, int r, int value) : l(l), r(r), value(value) {}
  } f[N * 20];

  int num = 1;
  inline void newChild(int s) { 
    if (!f[s].l) f[s].l = ++num, f[s].r = ++num;
  }

  void update(int s, int l, int r, int p, int x) { 
    if (p < l || p > r) return;
    if (l == r) { 
      f[s].value += x;
      return;
    }
    newChild(s);
    int mid = (l + r) >> 1;
    update(f[s].l, l, mid, p, x); update(f[s].r, mid + 1, r, p, x);
    f[s].value = f[f[s].l].value + f[f[s].r].value;
  }
  int query(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return 0;
    if (u <= l && r <= v) return f[s].value;
    newChild(s);
    int mid = (l + r) >> 1;
    return query(f[s].l, l, mid, u, v) + query(f[s].r, mid + 1, r, u, v);
  }

  inline void update(int p, int x) { 
    update(1, 1, MAX, p, x);
  }
  inline int query(int l, int r) { 
    return query(1, 1, MAX, l, r);
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m >> q;

  set<tuple<int, int, int>> s;
  s.emplace(1, n, 1);

  auto cut = [&](int pos) { 
    auto it = prev(s.upper_bound(tuple(pos, n + 1, 0)));
    
    auto [l, r, st] = *it;
    s.erase(it);
    if (l < pos) s.insert(tuple(l, pos - 1, st));
    if (pos <= r) s.insert(tuple(pos, r, st + pos - l));
  };

  set<int> pos;
  for (int i = 1; i <= n; ++i) pos.insert(i);

  for (int i = 1, time = 1; i <= m; ++i) { 
    int l, r; cin >> l >> r;
    
    { // first time
      vector<int> del;
      for (auto it = pos.lower_bound(l); it != pos.end() && *it <= r; ++it) { 
        del.push_back(*it);
        IT::update(time - l, -1);
      }
      for (const auto& x : del) pos.erase(x);
    }

    cut(l); cut(r + 1);
    vector<tuple<int, int, int>> del;
    for (auto it = s.lower_bound(tuple(l, 0, 0)); it != s.end() && get<1>(*it) <= r; ++it) { 
      const auto& [le, ri, st] = *it;
      del.push_back(*it);
      IT::update(time + le - l - st, ri - le + 1);
    }
    for (const auto& TP : del) s.erase(TP);
    s.insert(tuple(l, r, time));
    time += r - l + 1;
  }

  while (q--) { 
    int s; cin >> s;
    cout << IT::query(s + 1, MAX) << " \n"[!q];
  }
}

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