oj.uz

Submission #411778

# Submission time Handle Problem Language Result Execution time Memory
411778 2021-05-25T22:43:07 Z JerryLiu06 Editor (BOI15_edi) C++17
100 / 100
 216 ms 30288 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using db = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int MOD = 1e9 + 7;
const int MX = 3e5 + 10;
const ll INF = 1e18;

int N, state[MX], lev[MX]; int lift[MX][20];

// Get last node on path of X with level < maxLev ~ O(lg N)

int getLast(int X, int maxLev) {
    if (lev[X] < maxLev) return X;

    R0F(i, 20) if (lev[lift[X][i]] >= maxLev) X = lift[X][i]; return lift[X][0];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N; FOR(i, 1, N + 1) {
        cin >> state[i]; if (state[i] > 0) { cout << state[i] << "\n"; continue; }

        lev[i] = -state[i]; int lastActive = getLast(i - 1, lev[i]);

        lift[i][0] = getLast(lastActive - 1, lev[i]);
        FOR(j, 1, 20) lift[i][j] = lift[lift[i][j - 1]][j - 1];

        cout << state[getLast(i, 1)] << "\n";
    }
}

Compilation message

edi.cpp: In function 'int getLast(int, int)':
edi.cpp:40:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   40 | #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
      |                      ^~~
edi.cpp:41:19: note: in expansion of macro 'ROF'
   41 | #define R0F(i, a) ROF(i, 0, a)
      |                   ^~~
edi.cpp:58:5: note: in expansion of macro 'R0F'
   58 |     R0F(i, 20) if (lev[lift[X][i]] >= maxLev) X = lift[X][i]; return lift[X][0];
      |     ^~~
edi.cpp:58:63: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |     R0F(i, 20) if (lev[lift[X][i]] >= maxLev) X = lift[X][i]; return lift[X][0];
      |                                                               ^~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 780 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 29476 KB Output is correct
2 Correct 135 ms 29476 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8912 KB Output is correct
2 Correct 82 ms 10564 KB Output is correct
3 Correct 173 ms 22980 KB Output is correct
4 Correct 135 ms 29508 KB Output is correct
5 Correct 128 ms 30192 KB Output is correct
6 Correct 125 ms 27444 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 780 KB Output is correct
10 Correct 137 ms 29476 KB Output is correct
11 Correct 135 ms 29476 KB Output is correct
12 Correct 65 ms 8912 KB Output is correct
13 Correct 82 ms 10564 KB Output is correct
14 Correct 173 ms 22980 KB Output is correct
15 Correct 135 ms 29508 KB Output is correct
16 Correct 128 ms 30192 KB Output is correct
17 Correct 125 ms 27444 KB Output is correct
18 Correct 130 ms 17840 KB Output is correct
19 Correct 148 ms 17732 KB Output is correct
20 Correct 216 ms 28664 KB Output is correct
21 Correct 136 ms 29508 KB Output is correct
22 Correct 130 ms 30288 KB Output is correct