제출 #1288207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288207		vincentbucourt1	Shortcut (IOI16_shortcut)	C++20	71 / 100	2095 ms	11752 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long // careful of int !!!

const ll OO = (ll)1e14;

template<ll (*op)(ll&, ll&), ll NULLVAL>
struct Segtree {
    int numleaves;
    vector<ll> tree;
    Segtree (int n) {
        numleaves = 1;
        while (numleaves < n) numleaves *= 2;
        tree.assign(2*numleaves, NULLVAL);
    }
    ll query (int l, int r) {
        ll res = NULLVAL;
        l += numleaves, r += numleaves+1;
        while (l < r) {
            if (l&1) {
                res = op(res, tree[l++]);
            }
            if (r&1) {
                res = op(res, tree[--r]);
            }
            l /= 2, r /= 2;
        }
        return res;
    }
    void update (int idx, ll val) {
        idx += numleaves;
        tree[idx] = val;
        idx /= 2;
        while (idx > 0) {
            tree[idx] = op(tree[2*idx], tree[2*idx+1]);
            idx /= 2;
        }
    }
};
ll maxi (ll& a, ll& b) {return max(a, b);}
ll mini (ll& a, ll& b) {return min(a, b);}

bool test (ll UB, int& N, vector<ll>& dist, vector<int>& lenDown, const int& costBridge) {
    vector<int> incR(N, 0);
    iota(incR.begin(), incR.end(), 0);
    sort(incR.begin(), incR.end(), [&](const int& a, const int& b)->bool{
        return (dist[a] + lenDown[a] < dist[b] + lenDown[b]);
    });
    vector<int> decL(N, 0);
    iota(decL.begin(), decL.end(), 0);
    sort(decL.begin(), decL.end(), [&](const int& a, const int& b)->bool{
        return (-dist[a] + lenDown[a] > -dist[b] + lenDown[b]);
    });
    // x = r-l, y = r+l
    Segtree<maxi, -OO> xMinQ(N);
    Segtree<mini, OO> xMaxQ(N);
    Segtree<maxi, -OO> yMinQ(N);
    Segtree<mini, OO> yMaxQ(N);
    ll xMin = -OO, xMax = OO, yMin = -OO, yMax = OO;
    int iDecL = 0;
    for (int iIncR = 0; iIncR < N; iIncR++) {
        int iR = incR[iIncR];
        while (iDecL < N && (-dist[decL[iDecL]] + lenDown[decL[iDecL]]) > UB - (dist[iR] + lenDown[iR])) {
            int iL = decL[iDecL];
            xMinQ.update(iL, -dist[iL] + lenDown[iL]);
            xMaxQ.update(iL, -dist[iL] - lenDown[iL]);
            yMinQ.update(iL, dist[iL] + lenDown[iL]);
            yMaxQ.update(iL, dist[iL] - lenDown[iL]);
            iDecL++;
        }
        xMin = max(xMin, dist[iR] + lenDown[iR] - UB + costBridge + xMinQ.query(0, iR-1));
        xMax = min(xMax, dist[iR] - lenDown[iR] + UB - costBridge + xMaxQ.query(0, iR-1));
        yMin = max(yMin, dist[iR] + lenDown[iR] - UB + costBridge + yMinQ.query(0, iR-1));
        yMax = min(yMax, dist[iR] - lenDown[iR] + UB - costBridge + yMaxQ.query(0, iR-1));
    }
    // cerr << "UB: " << UB << ", " << xMin << " " << xMax << ", " << yMin << " " << yMax << "\n";
    bool res = false;
    for (int iL = 0; iL < N-1; iL++) {
        int iR = lower_bound(dist.begin(), dist.end(), max(xMin + dist[iL], yMin - dist[iL])) - dist.begin();
        if (iR < N && dist[iR] <= min(xMax + dist[iL], yMax - dist[iL])) {
            res = true;
        }
    }
    return res;
}

ll find_shortcut(int N, std::vector<int> lenSide, std::vector<int> lenDown, int costBridge) {
    vector<ll> dist(N, 0);
    for (int i = 0; i < N-1; i++) {
        dist[i+1] = dist[i] + lenSide[i];
    }
    ll loBS = 0, hiBS = OO;
    while (loBS < hiBS-1) {
        ll midBS = loBS + (hiBS - loBS) / 2;
        assert(loBS <= midBS && midBS <= hiBS);
        if (test(midBS, N, dist, lenDown, costBridge)) {
            hiBS = midBS;
        }
        else {
            loBS = midBS;
        }
    }
    return hiBS;
}

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

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3