oj.uz

답안 #241503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
241503 2020-06-24T10:02:28 Z osaaateiasavtnl Railway Trip (JOI17_railway_trip) C++17
30 / 100
 2000 ms 12272 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, INF = 1e9+7;
int n, k, q;
int a[N], ans[N];
int pref[N], suff[N];
int newl[N], newr[N];
vector <int> pos[N];
 
int par[N];
int root(int u) {
    if (par[u] == u)
        return u;
    else
        return par[u] = root(par[u]);
}
void merge(int u, int v) {
    if (u == 0 || v == 0)
        return;
    if (u > n || v > n)
        return;
    u = root(u);
    v = root(v);
    if (u != v) {
        par[u] = v;
    }
}   
 
int link_l[N], link_r[N];
 
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> k >> q; 
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
 
    vector <ii> d;
    for (int i = 0; i < q; ++i) {
        int u, v;
        cin >> u >> v;
        if (v < u)
            swap(u, v);
        d.app(mp(u, v));            
        ans[i] = INF;
    }   
 
    for (int i = 1; i <= k; ++i)
        pos[i].app(0);    
    for (int i = 1; i <= n; ++i)
        pos[a[i]].app(i);
    for (int i = 1; i <= k; ++i)
        pos[i].app(n+1);
 
    for (int i = 1; i <= n; ++i)
        par[i] = i;
 
    auto same_dist = [&](int i, int j) {
        int p1 = lower_bound(all(pos[a[i]]), i) - pos[a[i]].begin();
        int p2 = lower_bound(all(pos[a[j]]), j) - pos[a[j]].begin();
        return abs(p1-p2);
    };
 
    for (int x = 1; x <= k; ++x) {
        for (int i : pos[x]) {
            if (i && a[i - 1] <= x) {
                merge(i, i - 1);
            }   
            if (i + 1 <= n && a[i + 1] <= x) {
                merge(i, i + 1);
            }   
        }
 
        memset(link_l, 0, sizeof link_l);
        memset(link_r, 0, sizeof link_r);
        for (int i = 1; i <= n; ++i)
            newl[i] = newr[i] = INF;
 
        for (int i : pos[x]) {
            link_l[i] = link_r[i] = i;
            newl[i] = newr[i] = 0;
            for (int j = i - 1; j; --j) {
                if (a[j] >= a[i])
                    break;
                newr[j] = suff[j]+1;
                link_r[j] = i;
            }   
            for (int j = i + 1; j <= n; ++j) {
                if (a[j] >= a[i])
                    break;
                newl[j] = pref[j]+1;
                link_l[j] = i;
            }
        }   
 
        //pref - dist to nearest prefix maximum
        //suff - dist to nearest suffix maximum
        //newl - dist to nearest left x
        //newr - dist to nearest right x
        //link_l = number of the nearest left x
 
        auto getnewl = [&](int u) {
            return min(newl[u], newr[u]+1);
        };  
        auto getnewr = [&](int u) {
            return min(newl[u]+1, newr[u]);
        };  
 
        int lf = 0;
        for (int i = 1; i <= n; ++i) {
            if (a[i] > x) {
                lf = i;
                continue;
            }
            auto t = upper_bound(all(pos[x]), lf);
            if (*t <= i) {
                auto link = prev(upper_bound(all(pos[x]), i));
                pref[i] = getnewl(i) + (link - t);
            }   
            else if (link_r[i]) {
                pref[i] = min(pref[i], getnewr(i));
            }   
        }   
 
        int rf = n+1;
        for (int i = n; i; --i) {
            if (a[i] > x) {
                rf = i;
                continue;
            }   
            auto t = prev(upper_bound(all(pos[x]), rf));
            if (*t >= i) {
                auto link = lower_bound(all(pos[x]), i);
                suff[i] = getnewr(i) + (t - link);
            }   
            else if (link_l[i]) {
                suff[i] = min(suff[i], getnewl(i));
            }   
        }   
 
        for (int i = 0; i < q; ++i) {
            int u = d[i].f, v = d[i].s;
            if (root(u) == root(v)) {
                if (link_l[u] && link_l[v]) {
                    ans[i] = min(ans[i], getnewl(u) + getnewl(v) + same_dist(link_l[u], link_l[v]));
                }
                if (link_l[u] && link_r[v]) {
                    ans[i] = min(ans[i], getnewl(u) + getnewr(v) + same_dist(link_l[u], link_r[v]));
                }
                if (link_r[u] && link_l[v]) {
                    ans[i] = min(ans[i], getnewr(u) + getnewl(v) + same_dist(link_r[u], link_l[v]));
                }
                if (link_r[u] && link_r[v]) {
                    ans[i] = min(ans[i], getnewr(u) + getnewr(v) + same_dist(link_r[u], link_r[v]));
                }
            }
        }   
    }       
 
    for (int i = 0; i < q; ++i)
        cout << ans[i] - 1 << endl;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 3456 KB Output is correct
2 Correct 9 ms 3584 KB Output is correct
3 Correct 9 ms 3456 KB Output is correct
4 Correct 9 ms 3456 KB Output is correct
5 Correct 9 ms 3584 KB Output is correct
6 Correct 10 ms 3456 KB Output is correct
7 Correct 8 ms 3456 KB Output is correct
8 Correct 8 ms 3456 KB Output is correct
9 Correct 6 ms 3456 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 3584 KB Output is correct
2 Correct 82 ms 6776 KB Output is correct
3 Correct 118 ms 6776 KB Output is correct
4 Correct 197 ms 6776 KB Output is correct
5 Correct 320 ms 6712 KB Output is correct
6 Correct 1894 ms 6904 KB Output is correct
7 Execution timed out 2083 ms 10004 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 9456 KB Output is correct
2 Correct 213 ms 9584 KB Output is correct
3 Correct 227 ms 9456 KB Output is correct
4 Correct 231 ms 9452 KB Output is correct
5 Correct 248 ms 9580 KB Output is correct
6 Correct 249 ms 9712 KB Output is correct
7 Correct 249 ms 9584 KB Output is correct
8 Correct 173 ms 10224 KB Output is correct
9 Correct 194 ms 11248 KB Output is correct
10 Correct 283 ms 10884 KB Output is correct
11 Correct 305 ms 11376 KB Output is correct
12 Correct 324 ms 10864 KB Output is correct
13 Correct 288 ms 10868 KB Output is correct
14 Correct 186 ms 10092 KB Output is correct
15 Correct 213 ms 9812 KB Output is correct
16 Correct 250 ms 9456 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2080 ms 12272 KB Time limit exceeded
2 Halted 0 ms 0 KB -