Submission #1184871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184871		epicci23	Inspections (NOI23_inspections)	C++20	0 / 100	0 ms	584 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 2e5 + 5;

int fw[N];

inline void Upd(int c,int u){
  for(;c<N;c+=c&-c) fw[c] += u;
}

inline int Query(int c,int res = 0){
  for(;c;c-=c&-c) res += fw[c];
  return res;
}

void _(){
  int n, m, q;
  cin >> n >> m >> q;
  vector<int> Add[n+5],Omit[n+5];
  array<int,2> ar[m+5];

  for(int i=1;i<=m;i++){
  	int l,r;
  	cin >> l >> r;
    ar[i] = {l, r};
    Upd(i, r - l + 1);
  	Add[l].push_back(i);
  	Omit[r + 1].push_back(i);
  }

  auto Get = [&](int l,int r){
  	if(l >= r) return 0LL;
    int hm = Query(r - 1) - Query(l);
    hm += ar[l][1] - ar[r][0] + 1;
    return hm;
  };

  set<int> s;
  vector<int> freq(n+5,0), mark;

  auto Ekle = [&](int val){
    int l = -1, r = -1;
    auto it = s.lower_bound(val);
    if(it != s.end()) r = *it;
    if(it != s.begin()){
      it--;
      l = *it;
    }
    if(l != -1 && r != -1){
      freq[Get(l, r)]--;
      freq[Get(l, val)]++;
      freq[Get(val, r)]++;

      mark.push_back(Get(l, r));
      mark.push_back(Get(l, val));
      mark.push_back(Get(val, r));
    }
    else if(l != -1){
      freq[Get(l, val)]++;
      mark.push_back(Get(l, val));
    }
    else if(r != -1){
      freq[Get(val, r)]++;
      mark.push_back(Get(val, r));
    }

    s.insert(val);
  };

  auto Cikar = [&](int val){
    int l = -1, r = -1;
    s.erase(val);

    auto it = s.lower_bound(val);
    if(it != s.end()) r = *it;
    if(it != s.begin()){
      it--;
      l = *it;
    }
    if(l != -1 && r != -1){
      freq[Get(l, r)]++;
      freq[Get(l, val)]--;
      freq[Get(val, r)]--;

      mark.push_back(Get(l, r));
      mark.push_back(Get(l, val));
      mark.push_back(Get(val, r));
    }
    else if(l != -1){
      freq[Get(l, val)]--;
      mark.push_back(Get(l, val));
    }
    else if(r != -1){
      freq[Get(val, r)]--;
      mark.push_back(Get(val, r));
    }
  };
  
  vector<array<int,2>> v[n+5];

  for(int i=1;i<=n;i++){
    mark.clear();

    for(int u : Add[i]) Ekle(u);
    for(int u : Omit[i]) Cikar(u);
    
    for(int ind : mark) v[ind].push_back({i, freq[ind]});
  }

  vector<int> suf(n+5,0);

  for(int i=1;i<=n;i++){
  	for(int j = 0; j < sz(v[i]); j++){
  	  suf[i] += ((j == sz(v[i]) - 1 ? n + 1 : v[i][j + 1][0]) - v[i][j][0]) * v[i][j][1];
  	}
  }

  for(int i=n;i>=0;i--) suf[i] += suf[i+1];

  while(q--){
    int val;
    cin >> val;
    cout << suf[val + 1] << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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