oj.uz

답안 #225818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
225818 2020-04-21T18:40:21 Z VEGAnn Shortcut (IOI16_shortcut) C++14
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>
#include "shortcut.h"
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define ft first
#define sd second
using namespace std;
typedef long long ll;
const int N = 1000100;
const ll OO = 1e18;
pli events[N], o_events[N];
pll seg_mx[N], seg_mn[N];
ll pf[N], dst[N], c;
int n;

bool ok(ll mx){
    bool was = 0;
    ll u = -1, d = -1, l = -1, r = -1;

    int ptr = 0;

    for (register int it = 0; it < n; it++) {
        int i = o_events[it].sd;

        while (ptr < n && mx + events[ptr].ft < -pf[i] + dst[i])
            ptr++;

        pll cur = MP(1, 1);

        if (!(seg_mx[ptr].ft == -OO || (seg_mx[ptr].ft == (pf[i] + dst[i]) && seg_mx[ptr].sd == OO))) {

            cur.ft = (seg_mx[ptr].ft == (pf[i] + dst[i]) ? seg_mx[ptr].sd : seg_mx[ptr].ft);
            cur.sd = (seg_mn[ptr].ft == (pf[i] - dst[i]) ? seg_mn[ptr].sd : seg_mn[ptr].ft);

            ll cu = cur.sd + pf[i] + (mx - dst[i] - c);
            ll cd = cur.ft + pf[i] - (mx - dst[i] - c);
            ll cl = -cur.sd + pf[i] - (mx - dst[i] - c);
            ll cr = -cur.ft + pf[i] + (mx - dst[i] - c);

            if (!was){
                was = 1;
                u = cu; d = cd; l = cl; r = cr;
                if (u < d || r < l) return 0;
            } else {
                u = min(u, cu);
                d = max(d, cd);
                if (u < d) return 0;
                l = max(l, cl);
                r = min(r, cr);
                if (r < l) return 0;
            }
        }
    }

    if (!was) return 1;

    l >>= 1; r >>= 1;

    int l1 = n - 1, r1 = n;
    int r2 = -1, l2 = 0;

    for (register int i = 0; i < n; i++) {
        while (l1 - 1 >= 0 && pf[l1 - 1] + pf[i] >= d)
            l1--;
        while (r1 >= 0 && pf[r1] + pf[i] > u)
            r1--;

        while (r2 < n - 1 && ((pf[i] - pf[r2 + 1]) >> 1) >= l)
            r2++;
        while (l2 < n && ((pf[i] - pf[l2]) >> 1) > r)
            l2++;

        int j1 = max(l1, l2), j2 = min(r1, r2);

        if (j1 > j2) continue;

        if (j1 == j2){
            if (j1 != i)
                return 1;
        } else return 1;
    }

    return 0;
}

long long find_shortcut(int N, std::vector<int> l, std::vector<int> d, int C){
    n = N;
    c = C * 2;

    ll mex = 0;

    pf[0] = 0;

    for (register int i = 0; i < n - 1; i++) {
        pf[i + 1] = pf[i] + l[i] * 2;
        dst[i] = d[i] * 2;
        mex = max(mex, dst[i]);
    }

    dst[n - 1] = d[n - 1] * 2;
    mex = max(mex, dst[n - 1]);

    for (register int i = 0; i < n; i++) {
        events[i] = MP(-pf[i] - dst[i], i);
        o_events[i]= MP(-pf[i] + dst[i], i);
    }

    sort(events, events + n);
    sort(o_events, o_events + n);

    seg_mx[0] = MP(-OO, -OO);
    seg_mn[0] = MP(OO, OO);

    for (register int it = 1; it <= n; it++){
        int j = events[it - 1].sd;

        pll nw = MP(pf[j] + dst[j], pf[j] - dst[j]);

        seg_mx[it] = seg_mx[it - 1];
        seg_mn[it] = seg_mn[it - 1];

        if (seg_mx[it].ft < nw.ft){
            swap(seg_mx[it].ft, seg_mx[it].sd);
            seg_mx[it].ft = nw.ft;
        } else if (seg_mx[it].sd < nw.ft)
            seg_mx[it].sd = nw.ft;

        if (seg_mn[it].ft > nw.sd){
            swap(seg_mn[it].ft, seg_mn[it].sd);
            seg_mn[it].ft = nw.sd;
        } else if (seg_mn[it].sd > nw.sd)
            seg_mn[it].sd = nw.sd;
    }

    // smth smaller
    ll l1 = 0, r1 = mex + pf[n - 1] / 2;

    while (l1 < r1){
        ll md = (l1 + r1) >> 1;

        if (ok(md * 2))
            r1 = md;
        else l1 = md + 1;
    }

    ok(16);

    return l1;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 4 ms 384 KB n = 9, 110 is a correct answer
3 Correct 4 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 4 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 4 ms 384 KB n = 3, 29 is a correct answer
8 Correct 4 ms 384 KB n = 2, 3 is a correct answer
9 Correct 4 ms 384 KB n = 2, 3 is a correct answer
10 Correct 4 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 4 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 4 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 4 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 384 KB n = 10, 1000000343 is a correct answer
18 Incorrect 4 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 4 ms 384 KB n = 9, 110 is a correct answer
3 Correct 4 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 4 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 4 ms 384 KB n = 3, 29 is a correct answer
8 Correct 4 ms 384 KB n = 2, 3 is a correct answer
9 Correct 4 ms 384 KB n = 2, 3 is a correct answer
10 Correct 4 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 4 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 4 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 4 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 384 KB n = 10, 1000000343 is a correct answer
18 Incorrect 4 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 4 ms 384 KB n = 9, 110 is a correct answer
3 Correct 4 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 4 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 4 ms 384 KB n = 3, 29 is a correct answer
8 Correct 4 ms 384 KB n = 2, 3 is a correct answer
9 Correct 4 ms 384 KB n = 2, 3 is a correct answer
10 Correct 4 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 4 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 4 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 4 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 384 KB n = 10, 1000000343 is a correct answer
18 Incorrect 4 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 4 ms 384 KB n = 9, 110 is a correct answer
3 Correct 4 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 4 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 4 ms 384 KB n = 3, 29 is a correct answer
8 Correct 4 ms 384 KB n = 2, 3 is a correct answer
9 Correct 4 ms 384 KB n = 2, 3 is a correct answer
10 Correct 4 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 4 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 4 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 4 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 384 KB n = 10, 1000000343 is a correct answer
18 Incorrect 4 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 4 ms 384 KB n = 9, 110 is a correct answer
3 Correct 4 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 4 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 4 ms 384 KB n = 3, 29 is a correct answer
8 Correct 4 ms 384 KB n = 2, 3 is a correct answer
9 Correct 4 ms 384 KB n = 2, 3 is a correct answer
10 Correct 4 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 4 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 4 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 4 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 384 KB n = 10, 1000000343 is a correct answer
18 Incorrect 4 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 4 ms 384 KB n = 9, 110 is a correct answer
3 Correct 4 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 4 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 4 ms 384 KB n = 3, 29 is a correct answer
8 Correct 4 ms 384 KB n = 2, 3 is a correct answer
9 Correct 4 ms 384 KB n = 2, 3 is a correct answer
10 Correct 4 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 4 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 4 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 4 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 384 KB n = 10, 1000000343 is a correct answer
18 Incorrect 4 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 4 ms 384 KB n = 9, 110 is a correct answer
3 Correct 4 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 4 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 4 ms 384 KB n = 3, 29 is a correct answer
8 Correct 4 ms 384 KB n = 2, 3 is a correct answer
9 Correct 4 ms 384 KB n = 2, 3 is a correct answer
10 Correct 4 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 4 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 4 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 4 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 384 KB n = 10, 1000000343 is a correct answer
18 Incorrect 4 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB n = 4, 80 is a correct answer
2 Correct 4 ms 384 KB n = 9, 110 is a correct answer
3 Correct 4 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 4 ms 384 KB n = 2, 62 is a correct answer
6 Correct 4 ms 384 KB n = 2, 3 is a correct answer
7 Correct 4 ms 384 KB n = 3, 29 is a correct answer
8 Correct 4 ms 384 KB n = 2, 3 is a correct answer
9 Correct 4 ms 384 KB n = 2, 3 is a correct answer
10 Correct 4 ms 384 KB n = 2, 2000000001 is a correct answer
11 Correct 4 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 5 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 4 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 5 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 4 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 4 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 5 ms 384 KB n = 10, 1000000343 is a correct answer
18 Incorrect 4 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3115
19 Halted 0 ms 0 KB -