Submission #1211075

#TimeUsernameProblemLanguageResultExecution timeMemory
1211075TobPassport (JOI23_passport)C++20
0 / 100
2103 ms1007556 KiB
#include <bits/stdc++.h> #define F first #define S second #define all(x) x.begin(), x.end() #define pb push_back #define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; typedef long long ll; typedef pair <int, int> pii; const int N = 2e5 + 7, ofs = (1 << 18); int n; int l[N], r[N], t[2*ofs], d[2*ofs]; int f[2][N]; vector <int> td[2*N]; vector <pii> adj[2*ofs]; void add(int x, int y) { x += ofs; t[x] = y; while (x /= 2) t[x] = min(t[2*x], t[2*x+1]); } int get(int x, int l, int r, int lo = 0, int hi = ofs-1) { if (r < lo || hi < l) return ofs; if (l <= lo && hi <= r) return t[x]; int mid = (lo+hi)/2; return min(get(2*x, l, r, lo, mid), get(2*x+1, l, r, mid+1, hi)); } void dod(int x, int l, int r, int y, int lo = 0, int hi = ofs-1) { if (r < lo || hi < l) return; if (l <= lo && hi <= r) { adj[x].pb({y, 1}); return; } int mid = (lo+hi)/2; dod(2*x, l, r, y, lo, mid); dod(2*x+1, l, r, y, mid+1, hi); } int main () { FIO; cin >> n; for (int i = 1; i < ofs; i++) { adj[2*i].pb({i, 0}); adj[2*i+1].pb({i, 0}); } for (int i = 0; i < n; i++) { cin >> l[i] >> r[i]; l[i]--; r[i]--; } for (int o = 0; o < 2; o++) { fill(t, t+2*ofs, ofs); add(n-1, 0); for (int i = n-2; i >= 0; i--) { if (r[i] == i) f[o][i] = ofs; else if (r[i] < n-1) f[o][i] = get(1, i, r[i])+1; add(i, f[o][i]); } reverse(l, l+n); reverse(r, r+n); for (int i = 0; i < n; i++) { l[i] = n-l[i]-1; r[i] = n-r[i]-1; swap(l[i], r[i]); } } for (int i = 0; i < n; i++) { int x = f[0][i]+f[1][n-i-1]+1; if (x < ofs) td[x].pb(i+ofs); // dod(1, l[i], r[i], i+ofs); for (int j = l[i]; j <= r[i]; j++) adj[j+ofs].pb({i+ofs, 1}); } memset(d, -1, sizeof d); for (int i = 0; i < 2*N; i++) { while (!td[i].empty()) { int x = td[i].back(); td[i].pop_back(); if (d[x] != -1) continue; d[x] = i; for (auto y : adj[x]) { td[d[x]+y.S].pb(y.F); } } } int q; cin >> q; for (int i = 0; i < q; i++) { int x; cin >> x; cout << d[x-1+ofs] << "\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...