Submission #1133341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133341		duckindog	Inspections (NOI23_inspections)	C++17	55 / 100	1368 ms	1114112 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

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

deque<int> st[N / S + 10];
int assignValue[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 * 100];
  int lazy[N * 100];

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

    int mid = (l + r) >> 1;
    f[f[s].l].value += (mid - l + 1) * lazy[s];    
    lazy[f[s].l] += lazy[s];
    
    f[f[s].r].value += (r - mid) * lazy[s];    
    lazy[f[s].r] += lazy[s];

    lazy[s] = 0;
  }
  void update(int s, int l, int r, int u, int v, int x) { 
    if (v < l || u > r) return;
    newChild(s);
    if (u <= l && r <= v) { 
      f[s].value += (r - l + 1) * x;
      lazy[s] += x;
      return;
    }
    push(s, l, r);
    int mid = (l + r) >> 1;
    update(f[s].l, l, mid, u, v, x); update(f[s].r, mid + 1, r, u, v, 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;
    push(s, l, r);
    int mid = (l + r) >> 1;
    return query(f[s].l, l, mid, u, v) + query(f[s].r, mid + 1, r, u, v);
  }
}

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

  cin >> n >> m >> q;

  vector<tuple<int, int, int>> ranges;
  auto cal = [&](int block) { 
    int l = block * S - S + 1, r = min(block * S, n);
    if (assignValue[block] == -1) { 
      if (st[block].size()) { 
        for (int i = l; i <= r; ++i) {
          if (!a[i]) continue;
          ranges.emplace_back(st[block][0] - a[i] + i - l, 
                              st[block][0] - a[i] + i - l, 1);
        }
        iota(a + l, a + r + 1, assignValue[block] = st[block][0]);
        st[block].pop_front();
      }
    }
    
    for (const auto& value : st[block]) { 
      int dist = value - assignValue[block];
      ranges.emplace_back(dist, dist, r - l + 1);
      assignValue[block] = value;
    }
    st[block].clear();
  };

  int time = 1;
  auto upd = [&](int l, int r) { 
    int block = (l - 1) / S + 1;
    cal(block);
    
    if (assignValue[block] != -1) { 
      int le = block * S - S + 1, ri = min(block * S, n); 
      iota(a + le, a + ri + 1, assignValue[block]);
      assignValue[block] = -1;
    }

    for (int i = l; i <= r; ++i, ++time) { 
      if (a[i]) ranges.emplace_back(time - a[i], time - a[i], 1);
      a[i] = time;
    }
  };

  { // square root
    memset(assignValue, -1, sizeof assignValue);
    for (int i = 1; i <= m; ++i) { 
      int l, r; cin >> l >> r;

      int blockL = (l - 1) / S + 1, blockR = (r - 1) / S + 1;
      if (blockL == blockR) {
        upd(l, r);
      } else { 
        upd(l, blockL * S);
        for (int block = blockL + 1; block < blockR; ++block, time += S)
          st[block].push_back(time);
        upd(blockR * S - S + 1, r);
      }
    }
  }

  for (int block = 1; block <= (n - 1) / S + 1; ++block) 
    cal(block);

  for (const auto& [l, r, cnt] : ranges) 
    IT::update(1, 1, MAX, l, r, cnt);
  
  while (q--) { 
    int s; cin >> s;
    cout << IT::query(1, 1, MAX, s + 1, MAX) << " \n"[!q];
  }
}

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