제출 #1335774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1335774		SmuggingSpun	Inspections (NOI23_inspections)	C++20	100 / 100	1134 ms	43660 KiB

Main

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
int n, m, q;
namespace sub1{
  void solve(){
    vector<int>l(m + 1), r(m + 1);
    for(int i = 1; i <= m; i++){
      cin >> l[i] >> r[i];
    }
    for(int _ = 0; _ < q; _++){
      ll s;
      int ans = 0;
      cin >> s;
      vector<int>last(n + 1, 0);
      for(int i = 1, day = 0; i <= m; i++){
        for(int j = l[i]; j <= r[i]; j++){
          if(last[j] != 0 && s + last[j] <= day){
            ans++;
          }
          last[j] = ++day;
        }
      }
      cout << ans << " ";
    }
  }
}
namespace sub2{
  void solve(){
    vector<int>last(n + 1, 0);
    vector<ll>d;
    for(int i = 1, day = 0; i <= m; i++){
      int l, r;
      cin >> l >> r;
      for(int j = l; j <= r; j++){
        if(last[j] != 0){
          d.push_back(day - last[j]);
        }
        last[j] = ++day;
      }
    }
    sort(d.begin(), d.end());
    for(int i = 0; i < q; i++){
      ll s;
      cin >> s;
      cout << int(d.size()) - (upper_bound(d.begin(), d.end(), s - 1) - d.begin()) << " ";
    }
  }
}
namespace sub345{
  const int lim = 2e5 + 5;
  const ll INF = 1e18;
  vector<int>event[lim];
  int l[lim], r[lim];
  ll f[lim];
  ll calc(int i, int j){
    return f[j - 1] - f[i] + r[i] - l[j];
  }
  map<ll, ll>cnt;
  void solve(){
    f[0] = 0;
    for(int i = 1; i <= m; i++){
      cin >> l[i] >> r[i];
      f[i] = f[i - 1] + r[i] - l[i] + 1;
      event[l[i]].push_back(i);
      event[r[i] + 1].push_back(-i);
    }
    set<int>s;
    for(int i = 1; i <= n; i++){
      for(int& j : event[i]){
        if(j > 0){
          auto it = s.lower_bound(j);
          if(it != s.end()){
            cnt[calc(j, *it)] += n - i + 1;
          }
          if(it != s.begin()){
            cnt[calc(*prev(it), j)] += n - i + 1;
            if(it != s.end()){
              cnt[calc(*prev(it), *it)] -= n - i + 1;
            }
          }
          s.insert(j);
        }
        else{
          s.erase(j = -j);
          auto it = s.lower_bound(j);
          if(it != s.end()){
            cnt[calc(j, *it)] -= n - i + 1;
          }
          if(it != s.begin()){
            cnt[calc(*prev(it), j)] -= n - i + 1;
            if(it != s.end()){
              cnt[calc(*prev(it), *it)] += n - i + 1;
            }
          }
        }
      }
    }
    ll cur = cnt[INF] = 0;
    for(auto it = cnt.rbegin(); it != cnt.rend(); it++){
      it->second = (cur += it->second);
    }
    for(int _ = 0; _ < q; _++){
      ll s;
      cin >> s;
      cout << cnt.lower_bound(s)->second << " ";
    }
  }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
  cin >> n >> m >> q;
  if(max({n, m, q}) <= 200){
    sub1::solve();
  }
  else if(max(n, m) <= 2000){
    sub2::solve();
  }
  else{
    sub345::solve();
  }
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:114:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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