제출 #1249762

#제출 시각아이디문제언어결과실행 시간메모리
1249762mr_finCurtains (NOI23_curtains)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int,int>; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; vector<pii> A(m); for(int i = 0; i < m; i++){ cin >> A[i].first >> A[i].second; // (l, r) } // 1) Sắp xếp theo l tăng, nếu tie thì r giảm sort(A.begin(), A.end(), [&](auto &x, auto &y){ if (x.first != y.first) return x.first < y.first; return x.second > y.second; }); // 2) Tìm nxt[0] và reach[0] vector<int> nxt0(m, -1), reach0(m); // Duy trì một max-heap (r, idx) để với mỗi i, // ta biết được những j trước i thỏa l_j <= r_i+1 priority_queue<pair<int,int>> pq; int j = 0; for(int i = 0; i < m; i++){ // đẩy vào heap tất cả j với l_j <= r_i+1 while(j < m && A[j].first <= A[i].second + 1){ pq.push({ A[j].second, j }); j++; } // trong heap, chọn j có r_j lớn nhất if(!pq.empty()){ auto [bestR, bestIdx] = pq.top(); nxt0[i] = bestIdx; } reach0[i] = A[i].second; } // 3) Dựng binary-lifting int LOG = 1; while((1<<LOG) <= m) LOG++; vector<vector<int>> nxt(LOG, vector<int>(m, -1)); vector<vector<int>> reach(LOG, vector<int>(m, 0)); // bước 0 for(int i = 0; i < m; i++){ nxt[0][i] = nxt0[i]; reach[0][i]= reach0[i]; } // bước k > 0 for(int k = 1; k < LOG; k++){ for(int i = 0; i < m; i++){ int mid = nxt[k-1][i]; if(mid == -1){ nxt[k][i] = -1; reach[k][i] = reach[k-1][i]; } else { nxt[k][i] = nxt[k-1][mid]; reach[k][i] = max(reach[k-1][i], reach[k-1][mid]); } } } // 4) Xử lý mỗi query while(q--){ int s, e; cin >> s >> e; // tìm firstCurtain: l <= s <= r int lo = 0, hi = m-1, first = -1; while(lo <= hi){ int mid = (lo+hi)/2; if(A[mid].first <= s){ if(A[mid].second >= s){ first = mid; break; } lo = mid+1; } else { hi = mid-1; } } if(first == -1){ cout << "NO\n"; continue; } // nếu ngay curtain đó đã phủ qua e if(reach0[first] >= e){ cout << "YES\n"; continue; } // doubling int cur = first; for(int k = LOG-1; k >= 0; k--){ if(cur == -1) break; if(reach[k][cur] < e){ cur = nxt[k][cur]; } } // check one more step if(cur != -1 && reach0[cur] >= e) cout << "YES\n"; else cout << "NO\n"; } return 0; }
#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...