oj.uz

Submission #974084

# Submission time Handle Problem Language Result Execution time Memory
974084 2024-05-02T18:33:15 Z mariaclara Shortcut (IOI16_shortcut) C++17
0 / 100
 2000 ms 2484 KB 
#include "shortcut.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const ll LINF = 1e18;
const int MAXN = 1e6+5;
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define mk make_pair 
#define pb push_back
#define f first
#define s second

ll seg[4*MAXN], p[MAXN], d_aux[MAXN];

void build(int node, int l, int r) {
    if(l == r) {
        seg[node] = p[l] + d_aux[l];
        return;
    }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    seg[node] = max(seg[2*node], seg[2*node+1]);
}

int query(int node, int l, int r, int i, int x) {
    if(r < i or seg[node] <= x) return -1;
    if(l == r) return l;
    int mid = (l+r)/2;
    int a = -1;
    if(seg[2*node] > x) a = query(2*node, l, mid, i, x);
    if(a != -1) return a;
    else return query(2*node+1, mid+1, r, i, x);
}

ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    for(int i = 1; i < n; i++) p[i] = p[i-1] + l[i-1];
    for(int i = 0; i < n; i++) d_aux[i] = d[i];
    build(1, 0, n-1);
    
    ll L = 0, R = 1e15;
    
    while(L <= R) {
        int mid = (L+R)/2; // checa se a resposta pode ser menor ou igual a mid

        vector<int> a(n); // a[i] é o primeiro cara tal que p[a[i]] - p[i] + d[a[i]] + d[i] > mid
        for(int i = 0; i < n; i++) {
            a[i] = query(1, 0, n-1, i+1, mid + p[i] - d[i]);
            if(a[i] == -1) a[i] = n;
        }

        vector<ll> maxsum(n+1), maxdif(n+1), minsum(n+1), mindif(n+1);
        maxsum[n] = maxdif[n] = LINF;
        minsum[n] = mindif[n] = -LINF;
        for(int i = n-1; i >= 0; i--) {
            maxsum[i] = min(maxsum[i+1], p[i] + mid - d[i] - c);
            minsum[i] = max(minsum[i+1], p[i] - mid + d[i] + c);
            maxdif[i] = min(maxdif[i+1], -p[i] + mid - d[i] - c);
            mindif[i] = max(mindif[i+1], -p[i] - mid + d[i] + c);
        }

        ll A = LINF, B = -LINF, C = LINF, D = -LINF;
        for(int i = 0; i < n; i++) {
            A = min(A, maxsum[a[i]] + p[i] - d[i]);
            B = max(B, minsum[a[i]] + p[i] + d[i]);
            C = min(C, maxdif[a[i]] + p[i] - d[i]);
            D = max(D, mindif[a[i]] + p[i] + d[i]);
        }

        // basta achar l, r tal que
        // B <= p[l] + p[r] <= A
        // D <= p[l] - p[r] <= C
        // max(B - p[l], p[l] - C) <= p[r] <= min(A - p[l], p[l] - D)

        bool poss_ans = 0;
        for(int i = 0; i < n; i++) { // l fixo
            int ind = lower_bound(p, p+n, max(B - p[i], p[i] - C)) - p;
            if(ind < n and p[ind] <= min(A - p[i], p[i] - D)) poss_ans = 1;
        }

        if(poss_ans) R = mid-1;
        else L = mid+1;
    }

    return R+1;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2404 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2396 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2396 KB n = 3, 4 is a correct answer
5 Correct 1 ms 2396 KB n = 2, 62 is a correct answer
6 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
7 Correct 1 ms 2396 KB n = 3, 29 is a correct answer
8 Correct 0 ms 2396 KB n = 2, 3 is a correct answer
9 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
10 Correct 1 ms 2396 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2032 ms 2484 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2404 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2396 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2396 KB n = 3, 4 is a correct answer
5 Correct 1 ms 2396 KB n = 2, 62 is a correct answer
6 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
7 Correct 1 ms 2396 KB n = 3, 29 is a correct answer
8 Correct 0 ms 2396 KB n = 2, 3 is a correct answer
9 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
10 Correct 1 ms 2396 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2032 ms 2484 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2404 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2396 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2396 KB n = 3, 4 is a correct answer
5 Correct 1 ms 2396 KB n = 2, 62 is a correct answer
6 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
7 Correct 1 ms 2396 KB n = 3, 29 is a correct answer
8 Correct 0 ms 2396 KB n = 2, 3 is a correct answer
9 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
10 Correct 1 ms 2396 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2032 ms 2484 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2404 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2396 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2396 KB n = 3, 4 is a correct answer
5 Correct 1 ms 2396 KB n = 2, 62 is a correct answer
6 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
7 Correct 1 ms 2396 KB n = 3, 29 is a correct answer
8 Correct 0 ms 2396 KB n = 2, 3 is a correct answer
9 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
10 Correct 1 ms 2396 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2032 ms 2484 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2404 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2396 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2396 KB n = 3, 4 is a correct answer
5 Correct 1 ms 2396 KB n = 2, 62 is a correct answer
6 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
7 Correct 1 ms 2396 KB n = 3, 29 is a correct answer
8 Correct 0 ms 2396 KB n = 2, 3 is a correct answer
9 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
10 Correct 1 ms 2396 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2032 ms 2484 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2404 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2396 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2396 KB n = 3, 4 is a correct answer
5 Correct 1 ms 2396 KB n = 2, 62 is a correct answer
6 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
7 Correct 1 ms 2396 KB n = 3, 29 is a correct answer
8 Correct 0 ms 2396 KB n = 2, 3 is a correct answer
9 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
10 Correct 1 ms 2396 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2032 ms 2484 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2404 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2396 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2396 KB n = 3, 4 is a correct answer
5 Correct 1 ms 2396 KB n = 2, 62 is a correct answer
6 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
7 Correct 1 ms 2396 KB n = 3, 29 is a correct answer
8 Correct 0 ms 2396 KB n = 2, 3 is a correct answer
9 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
10 Correct 1 ms 2396 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2032 ms 2484 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2404 KB n = 4, 80 is a correct answer
2 Correct 1 ms 2396 KB n = 9, 110 is a correct answer
3 Correct 1 ms 2396 KB n = 4, 21 is a correct answer
4 Correct 1 ms 2396 KB n = 3, 4 is a correct answer
5 Correct 1 ms 2396 KB n = 2, 62 is a correct answer
6 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
7 Correct 1 ms 2396 KB n = 3, 29 is a correct answer
8 Correct 0 ms 2396 KB n = 2, 3 is a correct answer
9 Correct 1 ms 2396 KB n = 2, 3 is a correct answer
10 Correct 1 ms 2396 KB n = 2, 2000000001 is a correct answer
11 Execution timed out 2032 ms 2484 KB Time limit exceeded
12 Halted 0 ms 0 KB -