oj.uz

Submission #225530

# Submission time Handle Problem Language Result Execution time Memory
225530 2020-04-20T19:43: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 = 300100;
const ll OO = 1e18;
vector<pli> events;
pll seg[4 * N]; // first - max, second - min
ll pf[N], dst[N], c;
int n, mem_l[N], mem_r[N];
bool mrk[N];

void build(int v, int l, int r){
    seg[v] = MP(-OO, OO);

    if (l == r){
        mrk[l] = 0;
        return;
    }

    int md = (l + r) >> 1;
    build(v + v, l, md);
    build(v + v + 1, md + 1, r);
}

void update(int v, int l, int r, int ps, pll nw){
    if (l == r){
        seg[v] = nw;
        return;
    }

    int md = (l + r) >> 1;
    if (ps <= md)
        update(v + v, l, md, ps, nw);
    else update(v + v + 1, md + 1, r, ps, nw);

    seg[v].ft = max(seg[v + v].ft, seg[v + v + 1].ft);
    seg[v].sd = min(seg[v + v].sd, seg[v + v + 1].sd);
}

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

    int ptr = 0;

    // you can optimize it
    events.clear();
    for (int i = 0; i < n; i++)
        events.PB(MP(mx - pf[i] - dst[i], i));

    sort(all(events));

    for (int i = 0; i < n; i++) {
        while (ptr < n && events[ptr].ft < -pf[i] + dst[i]){
            int j = events[ptr].sd;

            mrk[j] = 1;
            update(1, 0, n - 1, j, MP(pf[j] + dst[j], pf[j] - dst[j]));
            ptr++;
        }

        if (mrk[i]){
            update(1, 0, n - 1, i, MP(-OO, OO));
        }

        pll cur = seg[1];

        if (cur.ft == -OO) continue;

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

        if (!was){
            was = 1;
            u = cu; d = cd; l = cl; r = cr;
        } 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 (mrk[i]){
            update(1, 0, n - 1, i, MP(pf[i] + dst[i], pf[i] - dst[i]));
        }
    }

    if (!was) return 1;

    l /= 2; r /= 2;

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

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

        mem_l[i] = l1;
        mem_r[i] = r1;
    }

    for (int i = 0; i < n; i++) {
        while (r2 < n - 1 && (pf[i] - pf[r2 + 1]) / 2 >= l)
            r2++;
        while (l2 < n && (pf[i] - pf[l2]) / 2 > r)
            l2++;

        int j1 = max(mem_l[i], l2), j2 = min(mem_r[i], 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;

    assert(n <= 300000);

    pf[0] = 0;

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

    dst[n - 1] = d[n - 1] * 2;

    // smth smaller
    ll l1 = 0, r1 = OO;

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

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

    return l1 / 2;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 60
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 60
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 60
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 60
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 60
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 60
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 60
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB n = 4, incorrect answer: jury 80 vs contestant 60
2 Halted 0 ms 0 KB -