Submission #1211089

#TimeUsernameProblemLanguageResultExecution timeMemory
1211089TobPassport (JOI23_passport)C++20
100 / 100
614 ms116616 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], d[2*ofs]; int f[3][2*ofs]; vector <int> td[2*N]; vector <pii> adj[2*ofs]; 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]--; dod(1, l[i], r[i], i+ofs); } for (int o = 0; o < 3; o++) { if (!o) td[0].pb(ofs); else if (o == 1) td[0].pb(n-1+ofs); else { for (int i = 0; i < n; i++) if (f[0][i+ofs] != -1 && f[1][i+ofs] != -1) { td[f[0][i+ofs]+f[1][i+ofs]-1].pb(i+ofs); } } 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); } } } if (!o) d[ofs]++; if (o == 1) d[n-1+ofs]++; for (int i = 0; i < 2*ofs; i++) f[o][i] = d[i]; } int q; cin >> q; for (int i = 0; i < q; i++) { int x; cin >> x; cout << f[2][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...