Submission #730994

#TimeUsernameProblemLanguageResultExecution timeMemory
730994groguPassport (JOI23_passport)C++14
100 / 100
1751 ms424828 KiB
#define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include <bits/stdc++.h> #define ld double #define ll long long #define ull unsigned long long #define llinf 100000000000000000LL // 10^17 #define iinf 2000000000 // 2*10^9 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pii pair<int,int> #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() using namespace std; #define maxn 1000005 int n,q; pair<int,int> a[maxn]; vector<vector<pair<int,ll> > > g(maxn); vector<vector<pair<int,ll> > > g2(maxn); ll dis[maxn]; ll dis1[maxn]; int ls[maxn],rs[maxn],tsz = 0,root = 0; int id[maxn]; void upd(int x,int y,ll w){ g[x].pb({y,w}); g2[y].pb({x,w}); } void upd2(int x,int y,ll w){ //g2[x].pb({y,w}); } void init(int &v,int tl,int tr){ if(!v) v = ++tsz; if(tl==tr){ id[tl] = v; return; } int mid = (tl+tr)/2; init(ls[v],tl,mid); init(rs[v],mid+1,tr); upd(v,ls[v],0); upd2(ls[v],v,0); upd(v,rs[v],0); upd2(rs[v],v,0); } void upd(int v,int tl,int tr,int l,int r,int u){ if(l>r||l>tr||tl>r||tl>tr) return; if(tl>=l&&tr<=r){ upd(u,v,0); upd2(v,u,1); upd2(u,v,0); return; } ll mid = (tl+tr)/2; upd(ls[v],tl,mid,l,r,u); upd(rs[v],mid+1,tr,l,r,u); } bool cmp(ll x,ll y){return dis1[x]<dis1[y];} void getdis(int poc,bool f,vector<vector<pair<int,ll> > > g){ deque<ll> pq; if(!f){ for(int i = 1;i<=tsz;i++) dis[i] = llinf; dis[poc] = 0; pq.pb(poc); }else{ vector<ll> v; for(ll i = 1;i<=tsz;i++) if(dis1[i]<llinf) v.pb(i); for(ll i = 1;i<=tsz;i++) dis[i] = dis1[i]; sort(all(v),cmp); for(ll x : v) pq.pb(x); } while(pq.size()){ ll u = pq.front(); pq.pop_front(); for(pll p : g[u]){ ll s = p.fi; ll w = p.sc; if(dis[u]+w<dis[s]){ dis[s] = dis[u]+w; if(w) pq.pb(s); else pq.push_front(s); } } } } ll F[maxn]; int main(){ ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); cin >> n; init(root,1,n); for(ll i = 1;i<=n;i++){ cin >> a[i].fi >> a[i].sc; tsz++; upd(id[i],tsz,1); upd2(tsz,id[i],0); upd(1,1,n,a[i].fi,i-1,tsz); upd(1,1,n,i+1,a[i].sc,tsz); } getdis(id[1],0,g2); for(ll i = 1;i<=tsz;i++) dis1[i]+=dis[i]; getdis(id[n],0,g2); for(ll i = 1;i<=tsz;i++) dis1[i]+=dis[i]; getdis(-1,1,g2); cin >> q; while(q--){ ll x; cin >> x; ll ans = dis[id[x]]; if(ans>=llinf) ans = -1; cout<<ans<<endl; } return 0; } /** 4 1 3 2 4 2 3 4 4 1 1 5 1 5 2 4 2 3 3 5 1 5 1 3 **/
#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...