Submission #1077148

#TimeUsernameProblemLanguageResultExecution timeMemory
1077148thelegendary08Railway Trip (JOI17_railway_trip)C++14
0 / 100
2047 ms6168 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define pb push_back #define int long long #define vi vector<int> #define vvi vector<vector<int>> #define vll vector<long long int> #define vvll vector<vector<long long int>> #define pii pair<int, int> #define vpii vector<pair<int, int>> #define vc vector<char> #define vvc vector<vector<char>> #define vb vector<bool> #define mii map<int,int> #define mll map<long long int, long long int> #define mivi map<int,vector<int>> #define f0r(i,n) for(int i=0;i<n;i++) #define FOR(i,k,n) for(int i=k;i<n;i++) using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> os; signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); //ifstream cin(".in"); //ofstream cout(".out"); int n,k,q; cin>>n>>k>>q; vi v(n); f0r(i, n)cin>>v[i]; os s; vpii w(n); f0r(i, n){ w.pb({v[i], i}); } sort(w.begin(), w.end()); f0r(i, n){ } while(q--){ int a,b; cin>>a>>b; a--; b--; queue<int>q; q.push(a); //do we need to calculate l[a] and r[a] for each a to make it faster? //yes //insert from low to high, do lowerbound to find left and right? //pbds probably needed vi dist(n, 4e18); dist[a] = 0; vb vis(n, 0); vis[a] = 1; while(!q.empty()){ int node = q.front(); q.pop(); int nl = -1; int nr = -1; for(int i = node + 1; i < n; i++){ if(v[i] >= v[node]){ nr = i; break; } } for(int i = node - 1; i>=0; i--){ if(v[i] >= v[node]){ nl = i; break; } } if(nl != -1 && !vis[nl]){ q.push(nl); vis[nl] = 1; dist[nl] = min(dist[nl], dist[node] + 1); if(nl == b)break; } if(nr != -1 && !vis[nr]){ q.push(nr); vis[nr] = 1; dist[nr] = min(dist[nr], dist[node] + 1); if(nr == b)break; } } cout<<dist[b]-1<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...