oj.uz

Submission #802728

# Submission time Handle Problem Language Result Execution time Memory
802728 2023-08-02T13:44:36 Z thimote75 Editor (BOI15_edi) C++14
100 / 100
 71 ms 24644 KB 
#include <bits/stdc++.h>

using namespace std;

string to_string (string s) { return s; }

template <typename T> string to_string (T A) {
    string str = "[";
    bool first = true;

    for (const auto &p : A) {
        if (!first) str += ", ";
        str += to_string(p);
        first = false;
    }

    str += "]";
    return str;
}
template<typename A, typename B> string to_string (pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out () { cout << endl; }
template<typename Head, typename... Tail> void dbg_out (Head H, Tail... T) {
    cout << to_string(H) << " ";

    dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "): "; dbg_out(__VA_ARGS__);
#else
#define dbg(...)
#endif

using idata = vector<int>;
using bdata = vector<bool>;

using di = pair<int, int>;
using pq = priority_queue<di>;

using vpq = vector<pq>;

idata level;
idata state;
idata parent;

vpq hidden;

void merge (pq &target, pq &obj) {
    bool sw = false;
    if (target.size() < obj.size()) {
        sw = true;
        target.swap(obj);
    }
    
    while (obj.size() != 0) {
        target.push(obj.top());
        obj.pop();
    }
}

/*void show (pq queue) {
    while (queue.size() != 0) {
        int curr = queue.top().second; queue.pop();

        cout << "=== " << curr << " ===\n";
        show(hidden[curr]);
        cout << "END " << curr << " END\n";
    }
}*/

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

    int N;
    cin >> N;    

    level .resize(N + 1);
    state .resize(N + 1);
    parent.resize(N + 1, - 1);

    for (int i = 1; i <= N; i ++) {
        int x; cin >> x;

        level[i] = max(- x, 0);
        state[i] = max(x, 0);
    }

    hidden.resize(N + 1);

    pq curr, next;
    for (int i = N; i >= 1; i --) {
        idata news;

        next = pq();

        while (curr.size() != 0 && curr.top().first > level[i]) {
            int local = curr.top().second;
            curr.pop();

            merge(
                next,
                hidden[local]
            );

            parent[local] = i;
        }

        hidden[i].swap(curr);
        curr.swap(next);
        curr.push({ level[i], i });
    }

    for (int i = 1; i <= N; i ++) {
        if (level[i] != 0)
            state[i] = state[parent[i] - 1];
        
        cout << state[i] << "\n";
    }
}

Compilation message

edi.cpp: In function 'void merge(pq&, pq&)':
edi.cpp:53:10: warning: variable 'sw' set but not used [-Wunused-but-set-variable]
   53 |     bool sw = false;
      |          ^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 596 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 20740 KB Output is correct
2 Correct 71 ms 20948 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11296 KB Output is correct
2 Correct 37 ms 13128 KB Output is correct
3 Correct 50 ms 15504 KB Output is correct
4 Correct 58 ms 22132 KB Output is correct
5 Correct 66 ms 23676 KB Output is correct
6 Correct 41 ms 20356 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 58 ms 20740 KB Output is correct
11 Correct 71 ms 20948 KB Output is correct
12 Correct 29 ms 11296 KB Output is correct
13 Correct 37 ms 13128 KB Output is correct
14 Correct 50 ms 15504 KB Output is correct
15 Correct 58 ms 22132 KB Output is correct
16 Correct 66 ms 23676 KB Output is correct
17 Correct 41 ms 20356 KB Output is correct
18 Correct 59 ms 24644 KB Output is correct
19 Correct 55 ms 24112 KB Output is correct
20 Correct 58 ms 21228 KB Output is correct
21 Correct 57 ms 22192 KB Output is correct
22 Correct 62 ms 23652 KB Output is correct