oj.uz

Submission #108429

# Submission time Handle Problem Language Result Execution time Memory
108429 2019-04-29T11:34:43 Z tictaccat Shortcut (IOI16_shortcut) C++14
0 / 100
 4 ms 384 KB 
#include "shortcut.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll INF = 1e18;

struct ft{
    int N; vector<ll> trLow, trHigh;
    ft(int N): N(N), trLow(N+1,INF), trHigh(N+1,-INF) {}
    pair<ll,ll> find(int i) {
        ll low = INF; ll high = -INF;
        i++;
        while (i > 0) {
            low = min(low, trLow[i]);
            high = max(high, trHigh[i]);
            i -= i&-i;
        }
        return make_pair(low,high);
    }
    void upd(int i, ll x) {
        i++;
        trLow[i] = trHigh[i] = x;
        while (i <= N) {
            trLow[i] = min(trLow[i], x);
            trHigh[i] = max(trHigh[i],x);
            i += i&-i;
        }
    }
};

int n; ll c;
vector<ll> l,d,x;
vector<ll> vals;

bool check (ll k) {

    ll difMax = INF, difMin = -INF, sumMax = INF, sumMin = -INF;

    ft sums(n), difs(n);

    for (int i = n-1; i >= 0; i--) {
        ll delta0 = k - c - d[i];
        // for (int j = i+1; j < n; j++) {
        //     if (x[j] - x[i] + d[i] + d[j] <= k) continue;
        //     ll delta = delta0 - d[j];
        //     difMax = min(x[j] - d[j] - x[i] + delta0, difMax);
        //     difMin = max(x[j] + d[j] - x[i] - delta0, difMin);
        //     sumMax = min(x[j] - d[j] + x[i] + delta0, sumMax);
        //     sumMin = max(x[j] + d[j] + x[i] - delta0, sumMin);
        // }

       // cout << "i: " << i << "\n";

        int queryPos = (int)(lower_bound(vals.begin(),vals.end(),k+x[i]-d[i]+1) - vals.begin());

       // cout << "qPos: " << queryPos << "\n";

        pair<ll,ll> q1 = sums.find(n-1-queryPos);
        pair<ll,ll> q2 = difs.find(n-1-queryPos);

     //   cout << k+x[i]-d[i]+1 << " " << queryPos << "\n";

       // cout << q1.first << " " << q1.second << "\n";

        difMax = min(q2.first - x[i] + delta0, difMax);
        difMin = max(q1.second - x[i] - delta0, difMin);
        sumMax = min(q2.first + x[i] + delta0, sumMax);
        sumMin = max(q1.second + x[i] - delta0, sumMin);

        int z = find(vals.begin(),vals.end(),x[i]+d[i]) - vals.begin();

        sums.upd(n-1-z, x[i] + d[i]);
        difs.upd(n-1-z, x[i] - d[i]);

    //   cout << "updPos: " << find(vals.begin(),vals.end(),x[i]+d[i]) - vals.begin() << "\n";

//       cout << "\n";

    }

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (x[j] - x[i] < difMin) continue;
            if (x[j] - x[i] > difMax) continue;
            if (x[j] + x[i] < sumMin) continue;
            if (x[j] + x[i] > sumMax) continue;
            return true;
        }
    }
    return false;
}

long long find_shortcut(int nt, std::vector<int> lt, std::vector<int> dt, int ct) {

    n = nt; c = ct;
    l.insert(l.end(),lt.begin(), lt.end()); 
    d.insert(d.end(), dt.begin(), dt.end()); 
    x.resize(n); vals.resize(n); 

    for (int i = 1; i < n; i++) x[i] = x[i-1] + l[i-1]; //length sum from left to index i

    //values stuffs

    for (int i = 0; i < n; i++) vals[i] = x[i] + d[i];
    sort(vals.begin(),vals.end());

    //binary search

    ll k = 0;
    ll high = INF;

    for (ll b = high/2; b > 0; b /= 2) {
        while (k + b < high && !check(k+b)) {
            k += b;
          //  cout << k << "\n";
        }
    } 

    return k+1;

    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 256 KB n = 9, 110 is a correct answer
3 Correct 2 ms 256 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Correct 2 ms 256 KB n = 2, 62 is a correct answer
6 Correct 2 ms 384 KB n = 2, 3 is a correct answer
7 Correct 2 ms 384 KB n = 3, 29 is a correct answer
8 Correct 2 ms 256 KB n = 2, 3 is a correct answer
9 Correct 3 ms 256 KB n = 2, 3 is a correct answer
10 Correct 3 ms 256 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 256 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 3 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 3 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 4 ms 256 KB n = 10, 1000000343 is a correct answer
18 Incorrect 2 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3167
19 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 256 KB n = 9, 110 is a correct answer
3 Correct 2 ms 256 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Correct 2 ms 256 KB n = 2, 62 is a correct answer
6 Correct 2 ms 384 KB n = 2, 3 is a correct answer
7 Correct 2 ms 384 KB n = 3, 29 is a correct answer
8 Correct 2 ms 256 KB n = 2, 3 is a correct answer
9 Correct 3 ms 256 KB n = 2, 3 is a correct answer
10 Correct 3 ms 256 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 256 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 3 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 3 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 4 ms 256 KB n = 10, 1000000343 is a correct answer
18 Incorrect 2 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3167
19 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 256 KB n = 9, 110 is a correct answer
3 Correct 2 ms 256 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Correct 2 ms 256 KB n = 2, 62 is a correct answer
6 Correct 2 ms 384 KB n = 2, 3 is a correct answer
7 Correct 2 ms 384 KB n = 3, 29 is a correct answer
8 Correct 2 ms 256 KB n = 2, 3 is a correct answer
9 Correct 3 ms 256 KB n = 2, 3 is a correct answer
10 Correct 3 ms 256 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 256 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 3 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 3 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 4 ms 256 KB n = 10, 1000000343 is a correct answer
18 Incorrect 2 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3167
19 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 256 KB n = 9, 110 is a correct answer
3 Correct 2 ms 256 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Correct 2 ms 256 KB n = 2, 62 is a correct answer
6 Correct 2 ms 384 KB n = 2, 3 is a correct answer
7 Correct 2 ms 384 KB n = 3, 29 is a correct answer
8 Correct 2 ms 256 KB n = 2, 3 is a correct answer
9 Correct 3 ms 256 KB n = 2, 3 is a correct answer
10 Correct 3 ms 256 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 256 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 3 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 3 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 4 ms 256 KB n = 10, 1000000343 is a correct answer
18 Incorrect 2 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3167
19 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 256 KB n = 9, 110 is a correct answer
3 Correct 2 ms 256 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Correct 2 ms 256 KB n = 2, 62 is a correct answer
6 Correct 2 ms 384 KB n = 2, 3 is a correct answer
7 Correct 2 ms 384 KB n = 3, 29 is a correct answer
8 Correct 2 ms 256 KB n = 2, 3 is a correct answer
9 Correct 3 ms 256 KB n = 2, 3 is a correct answer
10 Correct 3 ms 256 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 256 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 3 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 3 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 4 ms 256 KB n = 10, 1000000343 is a correct answer
18 Incorrect 2 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3167
19 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 256 KB n = 9, 110 is a correct answer
3 Correct 2 ms 256 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Correct 2 ms 256 KB n = 2, 62 is a correct answer
6 Correct 2 ms 384 KB n = 2, 3 is a correct answer
7 Correct 2 ms 384 KB n = 3, 29 is a correct answer
8 Correct 2 ms 256 KB n = 2, 3 is a correct answer
9 Correct 3 ms 256 KB n = 2, 3 is a correct answer
10 Correct 3 ms 256 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 256 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 3 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 3 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 4 ms 256 KB n = 10, 1000000343 is a correct answer
18 Incorrect 2 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3167
19 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 256 KB n = 9, 110 is a correct answer
3 Correct 2 ms 256 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Correct 2 ms 256 KB n = 2, 62 is a correct answer
6 Correct 2 ms 384 KB n = 2, 3 is a correct answer
7 Correct 2 ms 384 KB n = 3, 29 is a correct answer
8 Correct 2 ms 256 KB n = 2, 3 is a correct answer
9 Correct 3 ms 256 KB n = 2, 3 is a correct answer
10 Correct 3 ms 256 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 256 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 3 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 3 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 4 ms 256 KB n = 10, 1000000343 is a correct answer
18 Incorrect 2 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3167
19 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB n = 4, 80 is a correct answer
2 Correct 2 ms 256 KB n = 9, 110 is a correct answer
3 Correct 2 ms 256 KB n = 4, 21 is a correct answer
4 Correct 2 ms 384 KB n = 3, 4 is a correct answer
5 Correct 2 ms 256 KB n = 2, 62 is a correct answer
6 Correct 2 ms 384 KB n = 2, 3 is a correct answer
7 Correct 2 ms 384 KB n = 3, 29 is a correct answer
8 Correct 2 ms 256 KB n = 2, 3 is a correct answer
9 Correct 3 ms 256 KB n = 2, 3 is a correct answer
10 Correct 3 ms 256 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 256 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 384 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 3 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 3 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 4 ms 256 KB n = 10, 1000000343 is a correct answer
18 Incorrect 2 ms 384 KB n = 10, incorrect answer: jury 3189 vs contestant 3167
19 Halted 0 ms 0 KB -