Submission #745513

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
745513	2023-05-20T09:24:37 Z	boris_mihov	Shortcut (IOI16_shortcut)	C++17	0 / 100	0 ms	340 KB

shortcut

#include "shortcut.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
 
typedef long long llong;
const int MAXN = 1000000 + 10;
const llong INF = 1e16;

int n, c;
struct BIT
{
    llong tree[MAXN];
    void reset()
    {
        std::fill(tree + 1, tree + 1 + n, -INF);
    }

    void update(int pos, llong value)
    {
        for (int idx = pos ; idx <= n ; idx += idx & (-idx))
        {
            tree[idx] = std::max(tree[idx], value);
        }
    }

    llong query(int pos)
    {
        llong res = -INF;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            res = std::max(res, tree[idx]);
        }

        return res;
    }
};

BIT tree;
struct Point
{
    llong x, y;
};
 
struct Rectangle
{
    Point low, up;
    Rectangle()
    {
        low.x = low.y = -INF;
        up.x = up.y = INF;
    }
 
    bool isInside(Point p)
    {
        return low.x <= p.x && low.y <= p.y && p.x <= up.x && p.y <= up.y;
    }
};
 
int l[MAXN];
int d[MAXN];
int sortedPlus[MAXN];
int sortedMinus[MAXN];
llong p[MAXN];
 
bool check(llong allowed)
{
    tree.reset();
    Rectangle area;
    llong maxSub = -INF;
    int idxSum = 0;
    int idxSub = 0;
 
    for (int i = 1 ; i <= n ; ++i)
    {
        if (i > 1 && maxSub > allowed - d[i] - p[i])
        {
            area.low.y = std::max(area.low.y, p[i] + d[i] + maxSub + c - allowed);
            area.up.x = std::min(area.up.x, p[i] - d[i] - maxSub - c + allowed);
        }
 
        maxSub = std::max(maxSub, d[i] - p[i]);
    }
 
    llong maxSum;
    int ptr = n + 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (sortedPlus[i] == 1)
        {
            continue;
        }

        while (ptr > 1 && p[sortedPlus[i]] + d[sortedPlus[i]] - p[sortedMinus[ptr - 1]] + d[sortedMinus[ptr - 1]] > allowed)
        {
            ptr--;
            tree.update(sortedMinus[ptr], p[sortedMinus[ptr]] + d[sortedMinus[ptr]]);  
        }
 
        if (ptr <= n)
        {
            maxSum = tree.query(sortedPlus[i] - 1);
            area.low.x = std::max(area.low.x, p[sortedPlus[i]] + d[sortedPlus[i]] + maxSum + c - allowed);
            area.up.y = std::min(area.up.y, p[sortedPlus[i]] - d[sortedPlus[i]] - maxSum - c + allowed);
        }
    }
 
    ptr = 1;
    for (int i = n ; i > ptr ; --i)
    {
        while (ptr + 1 <= n && (p[ptr] + p[i] < area.low.x || p[i] - p[ptr] > area.up.y))
        {
            ptr++;
        }
 
        if (ptr < i)
        {
            Point curr = {p[i] + p[ptr], p[i] - p[ptr]};
            if (area.isInside(curr))
            {
                return true;
            }
        }
    }
 
    return false;
}
 
llong find_shortcut(int N, std::vector <int> L, std::vector <int> D, int C)
{
    n = N; c = C;
    for (int i = 0 ; i < n - 1 ; ++i)
    {
        l[i + 1] = L[i]; 
    }
 
    for (int i = 0 ; i < n ; ++i)
    {
        d[i + 1] = D[i];
    }
 
    p[1] = 0;
    for (int i = 2 ; i <= n ; ++i)
    {
        p[i] = p[i - 1] + l[i - 1];
    }
 
    std::iota(sortedPlus + 1, sortedPlus + 1 + n, 1);
    std::iota(sortedMinus + 1, sortedMinus + 1 + n, 1);
    std::sort(sortedPlus + 1, sortedPlus + 1 + n, [&](int x, int y)
    {
        return d[x] + p[x] < d[y] + p[y];
    });
 
    std::sort(sortedMinus + 1, sortedMinus + 1 + n, [&](int x, int y)
    {
        return d[x] - p[x] < d[y] - p[y];
    });
 
    llong l = -1, r = INF, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (!check(mid)) l = mid;
        else r = mid;
    }
 
    return r;
}

Compilation message

shortcut.cpp: In function 'bool check(llong)':
shortcut.cpp:73:9: warning: unused variable 'idxSum' [-Wunused-variable]
   73 |     int idxSum = 0;
      |         ^~~~~~
shortcut.cpp:74:9: warning: unused variable 'idxSub' [-Wunused-variable]
   74 |     int idxSub = 0;
      |         ^~~~~~

Subtask #1
0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	n = 4, 80 is a correct answer
2	Correct	340 KB	n = 9, 110 is a correct answer
3	Incorrect	340 KB	n = 4, incorrect answer: jury 21 vs contestant 22
4	Halted	0 KB	-

Subtask #2
0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	n = 4, 80 is a correct answer
2	Correct	340 KB	n = 9, 110 is a correct answer
3	Incorrect	340 KB	n = 4, incorrect answer: jury 21 vs contestant 22
4	Halted	0 KB	-

Subtask #3
0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	n = 4, 80 is a correct answer
2	Correct	340 KB	n = 9, 110 is a correct answer
3	Incorrect	340 KB	n = 4, incorrect answer: jury 21 vs contestant 22
4	Halted	0 KB	-

Subtask #4
0 / 7.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	n = 4, 80 is a correct answer
2	Correct	340 KB	n = 9, 110 is a correct answer
3	Incorrect	340 KB	n = 4, incorrect answer: jury 21 vs contestant 22
4	Halted	0 KB	-

Subtask #5
0 / 33.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	n = 4, 80 is a correct answer
2	Correct	340 KB	n = 9, 110 is a correct answer
3	Incorrect	340 KB	n = 4, incorrect answer: jury 21 vs contestant 22
4	Halted	0 KB	-

Subtask #6
0 / 22.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	n = 4, 80 is a correct answer
2	Correct	340 KB	n = 9, 110 is a correct answer
3	Incorrect	340 KB	n = 4, incorrect answer: jury 21 vs contestant 22
4	Halted	0 KB	-

Subtask #7
0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	n = 4, 80 is a correct answer
2	Correct	340 KB	n = 9, 110 is a correct answer
3	Incorrect	340 KB	n = 4, incorrect answer: jury 21 vs contestant 22
4	Halted	0 KB	-

Subtask #8
0 / 3.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	n = 4, 80 is a correct answer
2	Correct	340 KB	n = 9, 110 is a correct answer
3	Incorrect	340 KB	n = 4, incorrect answer: jury 21 vs contestant 22
4	Halted	0 KB	-