제출 #1339543

#제출 시각아이디문제언어결과실행 시간메모리
1339543SmuggingSpunCurtains (NOI23_curtains)C++20
100 / 100
755 ms114944 KiB
#include<bits/stdc++.h>
#define taskname "D"
using namespace std;
template<class T>void minimize(T& a, T b){
  if(a > b){
    a = b;
  }
}
template<class T>void maximize(T& a, T b){
  if(a < b){
    a = b;
  }
}
const int lim = 5e5 + 5;
int n, m, q, l[lim], r[lim], s[lim], e[lim];
namespace sub123{
  void solve(){
    vector<vector<int>>left(n + 1);
    for(int i = 1; i <= m; i++){
      left[r[i]].push_back(l[i]);
    }
    for(int i = 1; i <= n; i++){
      sort(left[i].begin(), left[i].end(), greater<int>());
    }
    vector<vector<bool>>ans(n + 1, vector<bool>(n + 1, false));
    for(int x = 1; x <= n; x++){
      for(int i = 1; i <= n; i++){
        while(!left[i].empty() && left[i].back() < x){
          left[i].pop_back();
        }
      }
      vector<int>f(n + 1, 0);
      for(int y = x; y <= n; y++){
        f[y] = f[y - 1];
        if(!left[y].empty() && (left[y].back() == x || f[y - 1] > f[left[y].back() - 2])){
          ans[x][y] = true;
          f[y]++;
        }
      }
    }
    for(int i = 1; i <= q; i++){
      cout << (ans[s[i]][e[i]] ? "YES\n" : "NO\n");
    }
  }
}
namespace sub4{
  void solve(){
    vector<vector<int>>event(n + 1);
    for(int i = 1; i <= m; i++){
      event[l[i]].push_back(r[i]);
    }
    vector<bool>ans(n + 1, false);
    priority_queue<int, vector<int>, greater<int>>pq;
    for(int i = 1; i <= n; i++){
      for(int& r : event[i]){
        pq.push(r);
      }
      while(!pq.empty() && pq.top() < i){
        pq.pop();
      }
      if(pq.empty()){
        break;
      }
      int r = pq.top();
      pq.pop();
      for(int j = i + 1; j <= r; j++){
        for(int& x : event[j]){
          pq.push(x);
        }
      }
      ans[i = r] = true;
    }
    for(int i = 1; i <= q; i++){
      cout << (ans[e[i]] ? "YES\n" : "NO\n");
    }
  }
}
namespace sub56{
  vector<int>range_id, event[lim], vst[lim << 2];
  int st[lim << 2];
  bitset<lim>ans;
  void update_vector(int p){
    int id = 1, l = 1, r = n;
    while(true){
      vst[id].push_back(p);
      if(l == r){
        break;
      }
      int m = (l + r) >> 1;
      id <<= 1;
      if(m < p){
        id |= 1;
        l = m + 1;
      }
      else{
        r = m;
      }
    }
  }
  void update_pos(int p, int x){
    int id = 1, l = 1, r = n;
    while(true){
      maximize(st[id], x);
      while(!vst[id].empty() && vst[id].back() >= p && vst[id].back() <= x){
        vst[id].pop_back();
      }
      if(l == r){
        break;
      }
      int m = (l + r) >> 1;
      id <<= 1;
      if(m < p){
        id |= 1;
        l = m + 1;
      }
      else{
        r = m;
      }
    }
  }
  void get_range(int id, int l, int r, int u, int v){
    if(l > v || r < u){
      return;
    }
    if(u <= l && v >= r){
      range_id.push_back(id);
      return;
    }
    int m = (l + r) >> 1;
    get_range(id << 1, l, m, u, v);
    get_range(id << 1 | 1, m + 1, r, u, v);
  }
  void solve(){
    memset(st, 0, sizeof(st));
    for(int i = 1; i <= m; i++){
      event[r[i]].push_back(i);
    }
    for(int i = 1; i <= q; i++){
      event[e[i]].push_back(-i);
    }
    ans.set();
    for(int i = 1; i <= n; i++){
      update_vector(i);
      for(int& id : event[i]){
        if(id > 0){
          update_pos(l[id], r[id]);
        }
        else{
          id = -id;
          range_id.clear();
          get_range(1, 1, n, s[id], e[id]);
          int best_right = 0;
          for(int& sid : range_id){
            if(!vst[sid].empty() && best_right < vst[sid].back()){
              ans[id] = false;
              break;
            }
            maximize(best_right, st[sid]);
          }
        }
      }
    }
    for(int i = 1; i <= q; i++){
      cout << (ans[i] ? "YES\n" : "NO\n");
    }
  }
}
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;
  for(int i = 1; i <= m; i++){
    cin >> l[i] >> r[i];
  }
  for(int i = 1; i <= q; i++){
    cin >> s[i] >> e[i];
  }
  if(n <= 2000){
    sub123::solve();
  }
  else if(*max_element(s + 1, s + q + 1) == 1){
    sub4::solve();
  }
  else{
    sub56::solve();
  }
}

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

curtains.cpp: In function 'int main()':
curtains.cpp:171:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...