Submission #1334502

#TimeUsernameProblemLanguageResultExecution timeMemory
1334502SmuggingSpunMi Teleférico (JOI25_ho_t3)C++20
100 / 100
707 ms144312 KiB
#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
template<class T>void minimize(T& a, T b){
  if(a > b){
    a = b;
  }
}
const int lim = 3e5 + 5;
const int INF = 1e9 + 36;
const int LIM = 12e5 + 5;
const int LG = 21;
struct Query{
  int l, r, x;
  Query(){}
  Query(int _l, int _r, int _x) : l(_l), r(_r), x(_x) {}
};
vector<Query>query;
vector<int>company(1, -1), edge[LIM];
int n, m, p, q, N, a[lim], b[lim], c[lim], lgv[LIM], spt[LG][LIM];
int company_id(int x){
  return lower_bound(company.begin(), company.end(), x) - company.begin();
}
int get_min(int l, int r){
  int k = lgv[r - l + 1];
  return min(spt[k][l], spt[k][r - (1 << k) + 1]);
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
  lgv[0] = -1;
  for(int i = 1; i < LIM; i++){
    lgv[i] = lgv[i >> 1] + 1;
  }
  cin >> n >> m >> p;
  for(int i = 1; i <= m; company.push_back(c[i++])){
    cin >> a[i] >> b[i] >> c[i];
  }
  cin >> q;
  query.resize(q);
  for(auto& [l, r, x] : query){
    cin >> l >> r >> x;
    company.push_back(l);
    company.push_back(r);
  }
  sort(company.begin(), company.end());
  company.resize(unique(company.begin(), company.end()) - company.begin());
  N = int(company.size()) - 1;
  for(int i = 1; i <= m; i++){
    edge[company_id(c[i])].push_back(i);
  }
  vector<int>best_r(N + 1, -1), best_l(N + 1, -1), in_deg(n + 1, 0);
  int siz = N;
  for(int l = 1, r = 1, cnt_0 = n - 1; l <= N; l++){
    while(r <= N && cnt_0 > 0){
      for(int& i : edge[r]){
        if(in_deg[b[i]]++ == 0){
          cnt_0--;
        }
      }
      r++;
    }
    if(cnt_0 > 0){
      siz = l - 1;
      break;
    }
    spt[0][l] = company[best_r[l] = r - 1] - company[l];
    for(int& i : edge[l]){
      if(--in_deg[b[i]] == 0){
        cnt_0++;
      }
    }
  }
  for(int i = 1; i < LG; i++){
    for(int j = 1; j + (1 << i) - 1 <= siz; j++){
      spt[i][j] = min(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]); 
    }
  }
  fill(in_deg.begin(), in_deg.end(), 0);
  for(int r = N, l = N, cnt_0 = n - 1; r > 0; r--){
    while(l > 0 && cnt_0 > 0){
      for(int& i : edge[l]){
        if(in_deg[b[i]]++ == 0){
          cnt_0--;
        }
      }
      l--;
    }
    if(cnt_0 > 0){
      break;
    }
    best_l[r] = l + 1;
    for(int& i : edge[r]){
      if(--in_deg[b[i]] == 0){
        cnt_0++;
      }
    }
  }
  for(auto& [l, r, x] : query){
    int lid = company_id(l), rid = company_id(r), best_cost = x + 1;
    if(best_r[lid] != -1){
      minimize(best_cost, company[max(best_r[lid], rid)] - r);
    }
    if(best_l[rid] != -1){
      minimize(best_cost, l - company[min(best_l[rid], lid)]);
    }
    int low = 1, high = min(siz, lid), p = -1;
    while(low <= high){
      int mid = (low + high) >> 1;
      if(best_r[mid] >= rid){
        high = (p = mid) - 1;
      }
      else{
        low = mid + 1;
      }
    }
    if(p != -1){
      minimize(best_cost, get_min(p, min(siz, lid)) - r + l);
    }
    cout << (best_cost <= x ? "Yes\n" : "No\n");
  }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:31:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |                 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...