oj.uz

Submission #241935

# Submission time Handle Problem Language Result Execution time Memory
241935 2020-06-26T11:22:42 Z osaaateiasavtnl Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 9840 KB 
#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 1e5+7;
int a[N];
vector <int> g[N];
int d[N];

int dist(int S, int T) {
    for (int i = 0; i < N; ++i)
        d[i] = N;
    d[S] = 0;
    queue <int> q; q.push(S);
    while (q.size()) {
        int u = q.front(); q.pop();
        if (u == T)
            return d[u];

        for (int v : g[u])
            if (d[u]+1 < d[v]) {
                d[v] = d[u]+1;
                q.push(v);
            }   
    }   
    cout << "LMAO" << endl;
    exit(1);
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int n, k, q;
    cin >> n >> k >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    while (q--) {
        int l, r;
        cin >> l >> r;
        if (r < l)  
            swap(l, r);
    
        if (l == r) {
            cout << -1 << endl;
            continue;
        }                   

        vector <int> p = {l, r};

        {
        int mx = a[l];
        for (int i = l-1; i; --i) {
            if (a[i] >= mx) {
                p.app(i);
                mx = a[i];
            }   
        }
        }   

        if (l + 1 < r) {
            int pos = l+1;
            for (int i = l + 1; i < r; ++i) 
                if (a[i] > a[pos])  
                    pos = i;
            int mx = -1;
            for (int i = l + 1; i < pos; ++i) {
                if (a[i] >= mx) {
                    p.app(i);
                    mx = a[i];
                }   
            }   
            mx = -1;
            for (int i = r - 1; i > pos; --i) {
                if (a[i] >= mx) {
                    p.app(i);
                    mx = a[i];
                }   
            }   
            p.app(pos);
        }   

        {
        int mx = a[r];
        for (int i = r + 1; i <= n; ++i) {
            if (a[i] >= mx) {
                p.app(i);
                mx = a[i];
            }   
        }
        }

        sort(all(p));

        /*
        cout << "p : ";
        for (auto e : p)
            cout << e << ' ';
        cout << endl;
        */

        int u = -1, v = -1;
        for (int i = 0; i < p.size(); ++i) {
            if (p[i] == l) {
                u = i;
            }   
            if (p[i] == r) {
                v = i;
            }   
        }   

        for (int i = 0; i < N; ++i)
            g[i].clear();

        {
        vector <int> s;
        for (int i = 0; i < p.size(); ++i) {
            while (s.size() && a[p[s.back()]] <= a[p[i]]) {
                g[s.back()].app(i);
                g[i].app(s.back());
                s.pop_back();
            }   
            s.app(i);
        }
        }

        {
        vector <int> s;
        for (int i = (int)p.size() - 1; i >= 0; --i) {
            while (s.size() && a[p[s.back()]] <= a[p[i]]) {
                g[s.back()].app(i);
                g[i].app(s.back());
                s.pop_back();
            }   
            s.app(i);
        }
        }   

        cout << dist(u, v) - 1 << endl;
    }   
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3072 KB Output is correct
2 Correct 11 ms 3072 KB Output is correct
3 Correct 11 ms 3072 KB Output is correct
4 Correct 11 ms 3072 KB Output is correct
5 Correct 11 ms 3072 KB Output is correct
6 Correct 11 ms 3072 KB Output is correct
7 Correct 11 ms 3072 KB Output is correct
8 Correct 11 ms 3072 KB Output is correct
9 Correct 11 ms 3072 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3072 KB Output is correct
2 Correct 95 ms 3840 KB Output is correct
3 Correct 66 ms 3832 KB Output is correct
4 Correct 53 ms 3584 KB Output is correct
5 Correct 43 ms 3456 KB Output is correct
6 Correct 41 ms 3456 KB Output is correct
7 Correct 43 ms 3456 KB Output is correct
8 Correct 554 ms 7632 KB Output is correct
9 Correct 417 ms 9840 KB Output is correct
10 Correct 456 ms 9824 KB Output is correct
11 Correct 320 ms 8656 KB Output is correct
12 Correct 329 ms 8556 KB Output is correct
13 Correct 373 ms 8764 KB Output is correct
14 Correct 346 ms 8948 KB Output is correct
15 Correct 374 ms 8536 KB Output is correct
16 Correct 357 ms 8712 KB Output is correct
17 Correct 45 ms 4096 KB Output is correct
18 Correct 44 ms 4096 KB Output is correct
19 Correct 43 ms 4096 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 4356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2093 ms 3556 KB Time limit exceeded
2 Halted 0 ms 0 KB -