Submission #1268775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268775		firegirlwaterboy	Circus (Balkan15_CIRCUS)	C++20	100 / 100	432 ms	16788 KiB

circus

#include "circus.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const int MAX_N = 1e5 + 2;
const ll MX64 = 1e18;

int posSize;
array<ll, MAX_N> rpos, rd, ld;
vector<pll> liner, linel;
vector<ll> ri, li;

void init(int N, int M, int P[]) {
    posSize = N;
    for (int i = 0; i < N; i++) {
        rpos[i] = P[i];
    }
    sort(rpos.begin(), rpos.begin() + N);
    rpos[N] = M;
    rd.fill(MX64), ld.fill(MX64);
    using T = pair<ll, pair<ll, bool>>;
    priority_queue<T, vector<T>, greater<T>> pq;
    ld[N] = 0, rd[N] = 0, ld[N - 1] = rpos[N] - rpos[N - 1];
    pq.push({rpos[N] - rpos[N - 1], {N - 1, false}});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        auto [i, rs] = u;
        pq.pop();
        if ((rs && rd[i] != d) || (!rs && ld[i] != d)) continue;
        if (rpos[i] - d >= rpos[0]) {
            ll pi =
                upper_bound(rpos.begin(), rpos.begin() + N + 1, rpos[i] - d) -
                rpos.begin();
            if (rpos[pi] > rpos[i] - d) pi--;
            if (ld[pi] > rpos[i] - rpos[pi]) {
                ld[pi] = rpos[i] - rpos[pi];
                pq.push({ld[pi], {pi, false}});
            }
        }
        if (rpos[i] + d < rpos[N]) {
            ll ni =
                lower_bound(rpos.begin(), rpos.begin() + N + 1, rpos[i] + d) -
                rpos.begin();
            if (rpos[ni] < rpos[i] + d) ni++;
            if (rd[ni] > rpos[ni] - rpos[i]) {
                rd[ni] = rpos[ni] - rpos[i];
                pq.push({rd[ni], {ni, true}});
            }
        }
        if (rs) {
            if (i < N) {
                ll ni = i + 1;
                if (rd[ni] > d + rpos[ni] - rpos[i]) {
                    rd[ni] = d + rpos[ni] - rpos[i];
                    pq.push({rd[ni], {ni, true}});
                }
            }
        } else {
            if (i > 0) {
                ll pi = i - 1;
                if (ld[pi] > d + rpos[i] - rpos[pi]) {
                    ld[pi] = d + rpos[i] - rpos[pi];
                    pq.push({ld[pi], {pi, false}});
                }
            }
        }
    }
    for (int i = 0; i <= N; ++i) {
        ll d = min(ld[i], rd[i]);
        linel.push_back({rpos[i] - d, d}), liner.push_back({rpos[i] + d, d});
    }
    sort(linel.begin(), linel.end()), sort(liner.begin(), liner.end());
    ll rVal = liner[0].second, rPos = liner[0].first;
    for (int i = 1; i < liner.size(); i++) {
        ll nVal = rVal + liner[i].first - rPos;
        if (liner[i].second > nVal) {
            liner[i].second = nVal;
        } else {
            rVal = liner[i].second;
            rPos = liner[i].first;
        }
    }
    ll lVal = linel[linel.size() - 1].second,
       lPos = linel[linel.size() - 1].first;
    for (int i = linel.size() - 2; i >= 0; --i) {
        ll nVal = lVal + lPos - linel[i].first;
        if (linel[i].second > nVal) {
            linel[i].second = nVal;
        } else {
            lVal = linel[i].second;
            lPos = linel[i].first;
        }
    }
    sort(linel.begin(), linel.end()), sort(liner.begin(), liner.end());
    for (int i = 0; i < liner.size(); i++) {
        ri.push_back(liner[i].first);
    }
    for (int i = 0; i < linel.size(); i++) {
        li.push_back(linel[i].first);
    }
}

int minLength(int D) {
    ll ans = MX64;
    auto r = upper_bound(ri.begin(), ri.end(), D) - ri.begin();
    if (ri[r] > D) r--;
    if (r >= 0) ans = min(ans, D - liner[r].first + liner[r].second);
    auto l = lower_bound(li.begin(), li.end(), D) - li.begin();
    if (li[l] < D) l++;
    if (l < linel.size()) ans = min(ans, linel[l].first - D + linel[l].second);
    return ans;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d%d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 scanf("%d", &P[i]);
      |                 ~~~~~^~~~~~~~~~~~~
grader.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
grader.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                 scanf("%d", &d);
      |                 ~~~~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 23 / 23
• Subtask 4: 9 / 9
• Subtask 5: 31 / 31
• Subtask 6: 9 / 9