oj.uz

Submission #813227

# Submission time Handle Problem Language Result Execution time Memory
813227 2023-08-07T14:23:43 Z trangtranha28 Circus (Balkan15_CIRCUS) C++14
100 / 100
 863 ms 26348 KB 
#include "circus.h"
#include <bits/stdc++.h>
using namespace std;
 
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<long long> 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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 8540 KB Output is correct
2 Correct 134 ms 10300 KB Output is correct
3 Correct 134 ms 10172 KB Output is correct
4 Correct 130 ms 10068 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 420 ms 17800 KB Output is correct
10 Correct 351 ms 10780 KB Output is correct
11 Correct 352 ms 10032 KB Output is correct
12 Correct 383 ms 18756 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 8540 KB Output is correct
2 Correct 134 ms 10300 KB Output is correct
3 Correct 134 ms 10172 KB Output is correct
4 Correct 130 ms 10068 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 144 ms 10300 KB Output is correct
14 Correct 132 ms 10264 KB Output is correct
15 Correct 123 ms 8464 KB Output is correct
16 Correct 123 ms 8440 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 8540 KB Output is correct
2 Correct 134 ms 10300 KB Output is correct
3 Correct 134 ms 10172 KB Output is correct
4 Correct 130 ms 10068 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 420 ms 17800 KB Output is correct
14 Correct 351 ms 10780 KB Output is correct
15 Correct 352 ms 10032 KB Output is correct
16 Correct 383 ms 18756 KB Output is correct
17 Correct 144 ms 10300 KB Output is correct
18 Correct 132 ms 10264 KB Output is correct
19 Correct 123 ms 8464 KB Output is correct
20 Correct 123 ms 8440 KB Output is correct
21 Correct 790 ms 20728 KB Output is correct
22 Correct 782 ms 22308 KB Output is correct
23 Correct 818 ms 25548 KB Output is correct
24 Correct 863 ms 26348 KB Output is correct