Submission #1184890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184890		epicci23	Inspections (NOI23_inspections)	C++20	100 / 100	1715 ms	95040 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,mark,Bul,Zip;

  auto Kordinat_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){
      Bul.push_back(Get(l, r));
      Bul.push_back(Get(l, val));
      Bul.push_back(Get(val, r));
    }
    else if(l != -1) Bul.push_back(Get(l, val));
    else if(r != -1) Bul.push_back(Get(val, r));
    
    s.insert(val);
  };

  auto Kordinat_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){
      Bul.push_back(Get(l, r));
      Bul.push_back(Get(l, val));
      Bul.push_back(Get(val, r));
    }
    else if(l != -1) Bul.push_back(Get(l, val));
    else if(r != -1) Bul.push_back(Get(val, r));
  };

  auto Upd_Freq = [&](int val,int u){
    int it = lower_bound(all(Bul), val) - Bul.begin();
    freq[it] += u;
  };

  auto Ekle = [&](int val, int flag){
    int l = -1, r = -1;

    if(flag == -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){
      Upd_Freq(Get(l, r),  -flag);
      Upd_Freq(Get(l, val), flag);
      Upd_Freq(Get(val, r), flag);

      mark.push_back(Get(l, r));
      mark.push_back(Get(l, val));
      mark.push_back(Get(val, r));
    }
    else if(l != -1){
      Upd_Freq(Get(l, val), flag);
      mark.push_back(Get(l, val));
    }
    else if(r != -1){
      Upd_Freq(Get(val, r), flag);
      mark.push_back(Get(val, r));
    }

    if(flag == 1) s.insert(val);
  };

  for(int i=1;i<=n;i++){
    for(int u : Add[i]) Kordinat_Ekle(u);
    for(int u : Omit[i]) Kordinat_Cikar(u);
  }

  Bul.push_back(0);
  sort(all(Bul));
  Bul.erase(unique(all(Bul)),Bul.end());
  s.clear();

  freq.assign(sz(Bul) + 2, 0);
  vector<array<int,2>> v[sz(Bul) + 2];

  for(int i=1;i<=n;i++){
  	mark.clear();
    for(int u : Add[i]) Ekle(u, 1);
    for(int u : Omit[i]) Ekle(u, -1);

    sort(all(mark));
    mark.erase(unique(all(mark)),mark.end());

    for(int u : mark){
      int it = lower_bound(all(Bul), u) - Bul.begin();
      v[it].push_back({i, freq[it]});
      //cout << "aha : " << i << ' ' << u << ' ' << freq[it] << '\n';
      Zip.push_back(u);
    }
  }
  
  vector<int> ans(q+5);
  for(int i=1;i<=q;i++){
  	cin >> ans[i];
  	Zip.push_back(ans[i] + 1);
  }
 
  for(int u : Bul) Zip.push_back(u);
  Zip.push_back(0);
  sort(all(Zip));
  Zip.erase(unique(all(Zip)),Zip.end());
  
  int sm = sz(Zip);
  vector<int> suf(sm+5,0);

  for(int i = 0; i < sz(Bul); i++){
  	int tot = 0;

  	for(int j = 0; j < sz(v[i]); j++){
  	  tot += ((j == sz(v[i]) - 1 ? n + 1 : v[i][j + 1][0]) - v[i][j][0]) * v[i][j][1];
  	}
     
    int xdd = lower_bound(all(Zip), Bul[i]) - Zip.begin();
  	suf[xdd] += tot;
  }

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

  for(int i=1;i<=q;i++){
    int val = ans[i];
    int hm = lower_bound(all(Zip), val + 1) - Zip.begin();
    cout << suf[hm] << '\n';
  }
}

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

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