oj.uz

Submission #1112266

# Submission time Handle Problem Language Result Execution time Memory
1112266 2024-11-14T00:42:29 Z ArtistWall Circus (Balkan15_CIRCUS) C++17
100 / 100
 876 ms 26436 KB 
#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 125 ms 9092 KB Output is correct
2 Correct 135 ms 10264 KB Output is correct
3 Correct 132 ms 10188 KB Output is correct
4 Correct 137 ms 10180 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 3 ms 2640 KB Output is correct
6 Correct 3 ms 2640 KB Output is correct
7 Correct 3 ms 2640 KB Output is correct
8 Correct 3 ms 2640 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 3 ms 2640 KB Output is correct
6 Correct 3 ms 2640 KB Output is correct
7 Correct 3 ms 2640 KB Output is correct
8 Correct 3 ms 2640 KB Output is correct
9 Correct 335 ms 19788 KB Output is correct
10 Correct 356 ms 12872 KB Output is correct
11 Correct 335 ms 11968 KB Output is correct
12 Correct 395 ms 18760 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 9092 KB Output is correct
2 Correct 135 ms 10264 KB Output is correct
3 Correct 132 ms 10188 KB Output is correct
4 Correct 137 ms 10180 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 3 ms 2640 KB Output is correct
10 Correct 3 ms 2640 KB Output is correct
11 Correct 3 ms 2640 KB Output is correct
12 Correct 3 ms 2640 KB Output is correct
13 Correct 131 ms 10436 KB Output is correct
14 Correct 136 ms 10360 KB Output is correct
15 Correct 136 ms 8700 KB Output is correct
16 Correct 136 ms 9092 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 9092 KB Output is correct
2 Correct 135 ms 10264 KB Output is correct
3 Correct 132 ms 10188 KB Output is correct
4 Correct 137 ms 10180 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 3 ms 2640 KB Output is correct
10 Correct 3 ms 2640 KB Output is correct
11 Correct 3 ms 2640 KB Output is correct
12 Correct 3 ms 2640 KB Output is correct
13 Correct 335 ms 19788 KB Output is correct
14 Correct 356 ms 12872 KB Output is correct
15 Correct 335 ms 11968 KB Output is correct
16 Correct 395 ms 18760 KB Output is correct
17 Correct 131 ms 10436 KB Output is correct
18 Correct 136 ms 10360 KB Output is correct
19 Correct 136 ms 8700 KB Output is correct
20 Correct 136 ms 9092 KB Output is correct
21 Correct 873 ms 20860 KB Output is correct
22 Correct 825 ms 22332 KB Output is correct
23 Correct 876 ms 25692 KB Output is correct
24 Correct 863 ms 26436 KB Output is correct