Submission #1116746

#TimeUsernameProblemLanguageResultExecution timeMemory
1116746hqminhuwuPassport (JOI23_passport)C++14
0 / 100
686 ms113948 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef long double ld; typedef vector <int> vi; typedef pair <ll,ll> pll; typedef pair <int,int> pii; typedef pair <int,pii> piii; #define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a) #define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);) #define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a) #define st first #define nd second #define pb push_back #define mp make_pair #define all(x) begin(x),end(x) #define mask(i) (1LL << (i)) #define bit(x, i) (((x) >> (i)) & 1) #define bp __builtin_popcountll #define file "test" template<class X, class Y> bool minz(X &x, const Y &y) { if (x > y) { x = y; return true; } return false; } template<class X, class Y> bool maxz(X &x, const Y &y) { if (x < y) { x = y; return true; } return false; } const int N = 5e5 + 5; const ll oo = (ll) 1e16; const ll mod = 1e9 + 7; // 998244353; int id[N], cnt; vector <pii> a[N << 2]; void build (int i, int l, int r){ cnt++; if (l == r){ id[l] = i; return; } int mid = l + r >> 1; build(i << 1, l, mid); build(i << 1 | 1, mid + 1, r); a[i << 1].pb({i, 0}); a[i << 1 | 1].pb({i, 0}); } void add (int i, int l, int r, int u, int v, int x){ if (l > v || r < u) return; if (l >= u && r <= v){ a[i].pb({x, 1}); return; } int mid = l + r >> 1; add(i << 1, l, mid, u, v, x); add(i << 1 | 1, mid + 1, r, u, v, x); } int n, l[N], r[N], d[3][N]; void go (int z){ priority_queue<pii, vector <pii>, greater<pii>> q; forr (i, 1, cnt){ q.push({d[z][i], i}); } while (!q.empty()) { pii t = q.top(); q.pop(); int u = t.nd; if (t.st != d[z][u] || t.st > n) continue; for (pii e : a[u]){ int v = e.st, w = e.nd; if (minz(d[z][v], d[z][u] + w)){ q.push({d[z][v], v}); } } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef kaguya freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); #endif cin >> n; build(1, 1, n); forr (i, 1, n){ cin >> l[i] >> r[i]; add(1, 1, n, l[i], r[i], id[i]); } memset (d, 63, sizeof d); d[0][id[1]] = 0; go(0); d[1][id[n]] = 0; go(1); forr (i, 1, n){ int u = id[i]; if (max(d[0][u], d[1][u]) > n){ continue; } d[2][u] = d[1][u] + d[0][u] - (i != n && i != 1); } go(2); int qq, zz; cin >> qq; while (qq--){ cin >> zz; zz = id[zz]; cout << (d[2][zz] <= n ? d[2][zz] : -1) << "\n"; } return 0; } /* */

Compilation message (stderr)

passport.cpp: In function 'void build(int, int, int)':
passport.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: In function 'void add(int, int, int, int, int, int)':
passport.cpp:64:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int mid = l + r >> 1;
      |               ~~^~~
#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...