Submission #1184877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184877		epicci23	Inspections (NOI23_inspections)	C++20	77 / 100	2099 ms	125552 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;
  map<int,int> freq;
  vector<int> 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));
    }
  };
  
  map<int,vector<array<int,2>>> v;

  vector<int> Zip;

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

    for(int u : Add[i]) Ekle(u);
    for(int u : Omit[i]) Cikar(u);
    
    /*if(i == n){
      cout << "suann : \n";
      for(auto X : freq){
        cout << X.first << ' ' << X.second << '\n';
      }

      for(int ind : mark) cout << ind << '\n';
    }*/
    
    for(int ind : mark){
      v[ind].push_back({i, freq[ind]});
      Zip.push_back(ind);
    }
  }

  vector<int> ans(q+5);
  for(int i=1;i<=q;i++){
  	cin >> ans[i];
  	Zip.push_back(ans[i]);
  	Zip.push_back(ans[i] + 1);
  }

  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(auto X : v){
  	int tot = 0;
  	for(int j = 0; j < sz(X.second); j++){
  	  tot += ((j == sz(X.second) - 1 ? n + 1 : X.second[j + 1][0]) - X.second[j][0]) * X.second[j][1];
  	}

  	int hm = lower_bound(all(Zip), X.first) - Zip.begin();
  	suf[hm] += 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: 0 / 23