Submission #70132

#	Time	Username	Problem	Language	Result	Execution time	Memory
70132		Inovak	Railway Trip (JOI17_railway_trip)	C++14	5 / 100	2061 ms	15572 KiB

railway_trip

#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define ll long long
#define OK puts("OK");
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 2e5+10;
const int inf = 1e9+7;

int n, k, q, s, f;
int L[N], l[N], r[N];
int d[N];
vector <pair <int, int> > g[N];

void go() {
    for(int i = 1; i <= n; i++) d[i] = inf;
    d[s] = 0;
    set <pair <int, int> > st;
    st.insert(mk(0, s));
    while(!st.empty()) {
        int v = st.begin()->sc;
        st.erase(st.begin());
        for(auto i : g[v]) {
            if(d[i.fr] > d[v] + i.sc) {
                st.erase(mk(d[i.fr], i.fr));
                st.insert(mk(d[i.fr] = d[v] + i.sc, i.fr));
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &k, &q);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &L[i]);
    }
    stack <int> st, si;
    st.push(inf);
    si.push(0);
    for(int i = 1; i <= n; i++) {
        while(st.top() < L[i]) {
            st.pop();
            si.pop();
        }
        l[i] = si.top();
        st.push(L[i]);
        si.push(i);
    }
    while(!st.empty()) st.pop(), si.pop();
    st.push(inf);
    si.push(n+1);
    for(int i = n; i >= 1; i--) {
        while(st.top() < L[i]) {
            st.pop();
            si.pop();
        }
        r[i] = si.top();
        st.push(L[i]);
        si.push(i);
    }

    while(q--) {
        scanf("%d%d", &s, &f);
        if(s == f) {puts("0");continue;}
        for(int i = 1; i <= n; i++) g[i].clear();
        for(int i = 1; i <= n; i++) {
            if(l[i] != 0) {
                g[i].pb(mk(l[i], 1));
                g[l[i]].pb(mk(i, 1));

            }
            if(r[i] != n+1) {
                g[i].pb(mk(r[i], 1));
                g[r[i]].pb(mk(i, 1));
            }
        }
//        int cnt = 1;
//        for(int i = f + 1; i <= n; i++) {
//            if(L[i] >= L[f]) {
//                g[i].pb(mk(f, cnt)); cnt++;
//            }
//        }
//        cnt = 1;
//        //g[f].pb(mk(f, 1));
//        for(int i = f - 1; i >= 1; i--) {
//            if(L[i] >= L[f]) {
//                g[i].pb(mk(f, cnt)); cnt++;
//            }
//        }
        go();
        printf("%d\n", d[f] - 1);
    }
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &k, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &L[i]);
         ~~~~~^~~~~~~~~~~~~
railway_trip.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &s, &f);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55