This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
template<typename T> bool maximize(T &x, const T &y) {
if (x < y) {x = y; return 1;}
return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
if (x > y) {x = y; return 1;}
return 0;
}
const int maxn = 2e5+5, INF = (int)1e9+7;
int n, trsz;
vector<int> adj[maxn*4];
int dis1[maxn*4], dis2[maxn*4], dis3[maxn*4];
namespace SMT{
void init() {
trsz = 1;
while (trsz < n) trsz <<= 1;
for (int i = trsz-1; i; i--) {
int lc = i<<1, rc = (i<<1)|1;
adj[lc].pb(i);
adj[rc].pb(i);
}
}
void buildedge(int u, int l, int r){
l += trsz - 1;
r += trsz;
u += trsz-1;
while (l < r){
if (l&1) {
adj[l++].pb(u);
}
if (r&1) {
adj[--r].pb(u);
}
l >>= 1;
r >>= 1;
}
}
}
void dijkstra(int dis[]) {
priority_queue<pii> q;
for (int i= 1; i < (trsz<<1); i++) {
q.push({-dis[i], i});
}
while (!q.empty()) {
int u = q.top().se, w = -q.top().fi;
q.pop();
if (w != dis[u]) continue;
if (dis[u] >= INF) continue;
for (int i= 0; i < (int)adj[u].size(); i++) {
int v = adj[u][i];
if (minimize(dis[v], dis[u]+(v>=trsz))) {
q.push({-dis[v], v});
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// #define name "task"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
//input + init SMT
cin >> n;
SMT::init();
//build graph
for (int i= 1; i <= n; i++) {
int l, r;
cin >> l >> r;
SMT::buildedge(i, l, r);
}
//dijkstra 12
memset(dis1, 0x3f, sizeof(dis1));
dis1[trsz] = 0;
dijkstra(dis1);
memset(dis2, 0x3f, sizeof(dis2));
dis2[trsz+n-1] = 0;
dijkstra(dis2);
//merge
memset(dis3, 0x3f, sizeof(dis3));
for (int i = 1; i <= n; i++) {
int u = i+trsz-1;
if (max(dis1[u], dis2[u]) >= INF) {
continue;
}
dis3[u] = dis1[u]+dis2[u]-1;
if (i == 1 || i == n) dis3[u]++;
}
//dijkstra 3
dijkstra(dis3);
// for (int i = 1; i < trsz*2; i++) {
// cout << "node " << i << ' ' << dis1[i] << ' ' << dis2[i] << ' ' << dis3[i] << "\n";
// }
//answer queries
int q;
cin >> q;
while (q--) {
int u;
cin >> u;
u += trsz - 1;
if (dis3[u] >= INF) cout << "-1\n";
else cout << dis3[u] << "\n";
}
}
# | 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... |