제출 #745521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745521		boris_mihov	Shortcut (IOI16_shortcut)	C++17	97 / 100	2076 ms	68756 KiB

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;
    llong l, r;
    for (int i = n ; i >= 2 ; --i)
    {
        l = std::max(area.low.x - p[i], p[i] - area.up.y);
        r = std::min(area.up.x - p[i], p[i] - area.low.y);

        while (ptr < i && p[ptr] < l && p[ptr + 1] <= r)
        {
            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;
}

컴파일 시 표준 에러 (stderr) 메시지

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: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 22 / 22
• Subtask 7: 4 / 4
• Subtask 8: 0 / 3