Submission #331987

#	Time	Username	Problem	Language	Result	Execution time	Memory
331987		ijxjdjd	Circus (Balkan15_CIRCUS)	C++11	100 / 100	1317 ms	26660 KiB

circus

#include "circus.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;

typedef pair<int, int> pi;
typedef  pair<long, long> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
struct st {
    public:
        int from;
        int t;
        int cur;
};
bool operator<(const st& lhs, const st& rhs) {
        return rhs.t < lhs.t;
}
const int MAXN = (int)(1e5) + 5;
int to[MAXN];
int from[MAXN+5];
bool seen[MAXN+5];
int ans[MAXN+5];
int sP[MAXN+5];
int s1[MAXN+5];
int s2[MAXN+5];
int Ns;
int findF(int i) {
    if (i == MAXN) {
        return MAXN;
    }
    if (seen[to[i]]) {
        to[i] = findF(to[i]);
    }
    return to[i];
}
int findB(int i) {
    if (i == MAXN){
        return MAXN;
    }
    if (seen[from[i]]) {
        from[i] = findB(from[i]);
    }
    return from[i];
}
set<pi> still;
priority_queue<st> pq;
void init(int N, int M, int P[]){
    sort(P, P+N);
    for (int i = 0; i < N; i++) {
        sP[i] = P[i];
    }
    sP[N] = M;
    for (int i = 0; i < N; i++) {
        still.insert({P[i], i});
    }
    fill(ans, ans+N, (int)(2e9));
    N++;
    Ns = N;
    seen[N-1] = true;
    from[0] = MAXN;
    to[N-1] = MAXN;
    ans[N-1] = 0;
    for (int i = 1; i < N; i++) {
        from[i] = i-1;
    }
    for (int i = 0; i < N-1; i++) {
        to[i] = i+1;
    }
    pq.push({N-1, M-P[N-2], N-2});
    ans[N-2] = M-P[N-2];
    while (still.size() > 0) {
        st next = pq.top();
        pq.pop();
        if (ans[next.cur] == next.t) {
            seen[next.cur] = true;
            still.erase({P[next.cur], next.cur});
            auto top = still.lower_bound({P[next.cur]+next.t, -1});
            auto bot = still.upper_bound({P[next.cur]-next.t, N});
            if (bot != still.begin()) {
                bot--;
                pq.push({next.cur, P[next.cur] - (*bot).first, (*bot).second});
                ans[(*bot).second] = min(ans[(*bot).second],  P[next.cur] - (*bot).first);
            }
            if (top != still.end()) {
                pq.push({next.cur, (*top).first - P[next.cur], (*top).second});
                ans[(*top).second] = min(ans[(*top).second], (*top).first - P[next.cur]);
            }
        }
        if (next.cur < next.from) {
            int n = findB(next.cur);
            if (n != MAXN) {
                pq.push({next.from, (next.from == N-1 ? M : P[next.from]) - P[n], n});
                ans[n] = min(ans[n], (next.from == N-1 ? M : P[next.from])-P[n]);
            }
        }
        else {
            int n = findF(next.cur);
            if (n != MAXN) {
                pq.push({next.from, P[n]-P[next.from], n});
                ans[n] = min(ans[n], P[n] - P[next.from]);
            }
        }
    }
    s1[N-1] = M;
    for (int i = N-2; i >= 0; i--) {
        s1[i] = P[i] - ans[i];
    }
    for (int i = 0; i < N; i++) {
        s2[i] = ans[i] + P[i];
    }
}
int minLength(int D) {
    int low = 0;
    int high = Ns-1;
    while (low < high) {
        int mid = (low + high)/2;
        if (sP[mid] <= D) {
            low = mid+1;
        }
        else {
            high = mid;
        }
    }
    int o1 = (int)(1e9);
    for (int i = high; i < Ns; i++) {
        if (s1[i] >= D) {
            o1 = sP[i]-D;
            break;
        }
    }
    low = 0;
    high = Ns-1;
    while (low < high) {
        int mid = (low + high+1)/2;
        if (sP[mid] >= D) {
            high = mid-1;
        }
        else {
            low = mid;
        }
    }
    for (int i = low; i >= 0; i--) {
        if (s2[i] <= D && D-sP[i] > 0) {
            return min(D-sP[i], o1);
        }
    }
    return o1;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
   14 |  long long max_code;
      |            ^~~~~~~~
grader.cpp:16:7: 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:8: 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:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
grader.cpp:23:8: 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