이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
constexpr int INF = 1e9;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
vector<pair<pii, int>> events(n);
vector<int> start(n), end(n);
map<int, int> mp;
for(int i = 0; i < n; i++) {
cin >> start[i] >> end[i];
events[i].first = {end[i], start[i]};
mp[start[i]] = mp[end[i]] = 1;
events[i].second = i;
}
int t = 0;
for(auto& [x, cmp] : mp)
cmp = t++;
sort(events.begin(), events.end());
int N = 1 << 32 - __builtin_clz(t - 1);
vector<pii> st(2 * N, {INF, -1});
vector<int> parent(n), jump(n), depth(n);
for(int i = 0; i < n; i++) {
int e = events[i].first.first, s = events[i].first.second;
pii ans = {INF, -1};
for(int l = N + mp[s], r = 2 * N; l < r; l >>= 1, r >>= 1) {
if(l & 1) ans = min(ans, st[l++]);
if(r & 1) ans = min(ans, st[--r]);
}
int v = events[i].second;
if(ans.second == -1 || ans.first >= mp[s])
jump[v] = parent[v] = v;
else {
int p = parent[v] = ans.second;
depth[v] = depth[p] + 1;
if(depth[p] - depth[jump[p]] == depth[jump[p]] - depth[jump[jump[p]]])
jump[v] = jump[jump[p]];
else
jump[v] = p;
}
for(int j = N + mp[e]; j > 0; j >>= 1)
st[j] = min(st[j], {mp[s], v});
}
while(q--) {
int x, y;
cin >> x >> y;
x--;
y--;
int d = depth[y];
while(x != y && parent[y] != y && start[parent[y]] >= start[x]) {
if(start[jump[y]] > start[x])
y = jump[y];
else
y = parent[y];
}
if(end[x] >= start[y] && end[x] <= end[y])
cout << (x!=y) + d - depth[y] << '\n';
else
cout << "impossible\n";
}
}
컴파일 시 표준 에러 (stderr) 메시지
events.cpp: In function 'int main()':
events.cpp:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
22 | for(auto& [x, cmp] : mp)
| ^
events.cpp:25:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
25 | int N = 1 << 32 - __builtin_clz(t - 1);
| ~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |