oj.uz

Submission #782534

# Submission time Handle Problem Language Result Execution time Memory
782534 2023-07-14T04:30:02 Z skittles1412 Editor (BOI15_edi) C++17
100 / 100
 83 ms 29900 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

struct FastCin {
    char buf[10 << 20], *i = buf;

    FastCin() {
        fread_unlocked(buf, 1, sizeof(buf), stdin);
    }

    FastCin& operator>>(int& x) {
        while (*i < '-') {
            i++;
        }

        bool neg = false;
        if (*i == '-') {
            neg = true;
            i++;
        }

        x = 0;

        while (*i >= '0') {
            x = x * 10 + (*(i++) ^ '0');
        }

        if (neg) {
            x = -x;
        }
        return *this;
    }
} in;

constexpr int logn = 19, maxn = 3e5 + 5;

int lift[logn][maxn];

void solve() {
    int n;
    in >> n;

    int arr[n];
    for (auto& a : arr) {
        in >> a;
        a = -a;
    }

    auto level = [&](int ind) -> int { return max(0, arr[ind]); };

    for (auto& a : lift) {
        fill(a, a + n, -1);
    }

    // first thing in stack u < x
    auto query = [&](int u, int x) -> int {
        if (u == -1) {
            return -1;
        } else if (level(u) < x) {
            return u;
        }
        for (int i = logn - 1; i >= 0; i--) {
            int nu = lift[i][u];
            if (nu != -1 && level(nu) >= x) {
                u = nu;
            }
        }
        return lift[0][u];
    };

    auto do_lift = [&](int u) -> void {
        for (int i = 1; i < logn; i++) {
            if (lift[i - 1][u] == -1) {
                lift[i][u] = -1;
            } else {
                lift[i][u] = lift[i - 1][lift[i - 1][u]];
            }
        }
    };

    int cst = -1;

    for (int i = 0; i < n; i++) {
        if (arr[i] > 0) {
            int undo = query(cst, arr[i]);
            assert(undo != -1);

            lift[0][i] = query(undo - 1, arr[i]);
            do_lift(i);
        }

        cst = i;

        int ans = query(cst, 1);
        if (ans == -1) {
            cout << 0 << endl;
        } else {
            cout << -arr[ans] << endl;
        }
    }
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}

Compilation message

edi.cpp: In constructor 'FastCin::FastCin()':
edi.cpp:32:23: warning: ignoring return value of 'size_t fread_unlocked(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         fread_unlocked(buf, 1, sizeof(buf), stdin);
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 852 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 28544 KB Output is correct
2 Correct 49 ms 28496 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 14884 KB Output is correct
2 Correct 29 ms 17684 KB Output is correct
3 Correct 78 ms 22916 KB Output is correct
4 Correct 47 ms 28584 KB Output is correct
5 Correct 49 ms 29888 KB Output is correct
6 Correct 39 ms 25788 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 48 ms 28544 KB Output is correct
11 Correct 49 ms 28496 KB Output is correct
12 Correct 24 ms 14884 KB Output is correct
13 Correct 29 ms 17684 KB Output is correct
14 Correct 78 ms 22916 KB Output is correct
15 Correct 47 ms 28584 KB Output is correct
16 Correct 49 ms 29888 KB Output is correct
17 Correct 39 ms 25788 KB Output is correct
18 Correct 48 ms 29800 KB Output is correct
19 Correct 47 ms 29596 KB Output is correct
20 Correct 83 ms 28340 KB Output is correct
21 Correct 47 ms 28492 KB Output is correct
22 Correct 46 ms 29900 KB Output is correct