Submission #1217723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217723		InvMOD	Circus (Balkan15_CIRCUS)	C++17	11 / 100	80 ms	4656 KiB

circus

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back

#define vi vector<int>
#define pi pair<int,int>
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())

template<class T> using upq = priority_queue<T, vector<T>, greater<T>>;
template<class T> int lwrbound(const vector<T>& a, const T& b, const int s = 0){return int(lower_bound(s + all(a), b) - a.begin());}
template<class T> int uprbound(const vector<T>& a, const T& b, const int s = 0){return int(upper_bound(s + all(a), b) - a.begin());}

#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define ROF(i, a, b) for(int i = (a); i >= (b); i--)
#define sumof(x) accumulate(all(x), 0ll)
#define dbg(x) "[" << #x " = " << (x) << "]"
#define el "\n"

//#define name "InvMOD"
#ifndef name
    #include "circus.h"
#endif // name

using ll = long long;
using ld = long double;

template<class T> bool ckmx(T& a, const T b){return (a < b ? a = b, true : false);}
template<class T> bool ckmn(T& a, const T b){return (a > b ? a = b, true : false);}

const int N = 2e5 + 5, INF = 2e9;

vector<int> posL, optL, posR, optR;

void init(int n, int m, int inP[]){
    vector<int> p; FOR(i, 0, n - 1) p.eb(inP[i]);
    p.eb(m); sort(all(p)); ++n;

    vector<int> dist(2 * n, INF);
    { // dijkstra
        int start = lwrbound(p, m); dist[start] = dist[start + n] = 0;

        priority_queue<pi> pq; pq.emplace(0, start); pq.emplace(0, start + n);
        while(sz(pq)){
            pi e = pq.top(); pq.pop();

            int x = e.se;
            if(e.fi > dist[x]) continue;

            // x can't go direct to next, so we have to increase the length
            auto cost = [&](int u, int v) -> int{
                u = (u < n ? u : u - n);
                v = (v < n ? v : v - n);

                return (p[u] - p[v] < 0 ? p[v] - p[u] : p[u] - p[v]);
            };
            if(x < n){
                // go up
                int nxt = x + 1;
                if(nxt < n){
                    if(p[nxt] - p[x] < dist[x]){
                        if(ckmn(dist[nxt], dist[x] + cost(nxt, x))){
                            pq.emplace(-dist[nxt], nxt);
                        }
                    }
                }
            }
            else{
                // go down

                int nxt = x - 1;
                if(nxt >= 0){
                    if(p[nxt - n] - p[x - n] < dist[x]){
                        if(ckmn(dist[nxt], dist[x] + cost(nxt, x))){
                            pq.emplace(-dist[nxt], nxt);
                        }
                    }
                }
            }

            // x can go directly to next now (require: abs(p[next] - p[x]) >= dist[x])
            int nxtU = lwrbound(p, p[x % n] + dist[x]);
            if(nxtU < n && cost(x, nxtU) >= dist[x]){
                if(ckmn(dist[nxtU], cost(x, nxtU))){
                    pq.emplace(-dist[nxtU], nxtU);
                }
            }

            int nxtD = uprbound(p, p[x % n] - dist[x]) - 1 + n;
            if(nxtD >= n){
                if(ckmn(dist[nxtD], cost(x, nxtD))){
                    pq.emplace(-dist[nxtD], nxtD);
                }
            }
        }
    }

    // p[i] > d -> require: p[i] - d >= dist[i] -> p[i] - dist[i] >= d (1)
    // the answer will be p[i] - d so we will take the minimum p[i] that has (1)
    {
        vector<pi> comp;
        FOR(i, 0, n - 1){
            int d = min(dist[i], dist[i + n]);

            comp.eb(p[i] - d, p[i]);
        }

        sort(all(comp), greater<pi>());
        for(pair<int,int> e : comp){
            int req = e.fi, pos = e.se;

            if(!sz(posR) || req != posR.back()){
                posR.eb(req);
                optR.eb(pos);
            }
            else ckmn(optR.back(), pos);
        }

        FOR(i, 1, sz(posR) - 1) ckmn(posR[i], posR[i - 1]);
        reverse(all(posR)), reverse(all(optR));
    }

    // p[i] < d -> require: d - p[i] >= dist[i] -> d >= dist[i] + p[i] (2)
    // the answer will be d - p[i] so we will take the maximum that has (2)
    {
        vector<pi> comp;
        FOR(i, 0, n - 1){
            int d = min(dist[i], dist[i + n]);

            comp.eb(p[i] + d, p[i]);
        }

        sort(all(comp));
        for(pair<int,int> e : comp){
            int req = e.fi, pos = e.se;

            if(!sz(posL) || posL.back() != req){
                posL.eb(req);
                optL.eb(pos);
            }
            else ckmx(optL.back(), pos);
        }

        FOR(i, 1, sz(posL) - 1) ckmx(optL[i], optL[i - 1]);
    }
}

int minLength(int d){
    int ans = 2e9;

    int pL = uprbound(posL, d) - 1;
    if(pL >= 0){
        ckmn(ans, d - optL[pL]);
    }

    int pR = lwrbound(posR, d);
    if(pR < sz(posR)){
        ckmn(ans, optR[pR] - d);
    }
    return ans;
}

#ifdef name
    int32_t main()
    {
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);

        int n,m; cin >> n >> m;

        int p[n]; FOR(i, 0, n - 1) cin >> p[i];

        init(n, m, p);

        int q; cin >> q;

        while(q--){
            int d; cin >> d;

            cout << minLength(d) << el;
        }
        return 0;
    }
#endif // name

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: 0 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 9
• Subtask 5: 0 / 31
• Subtask 6: 0 / 9