Submission #802728

#	Time	Username	Problem	Language	Result	Execution time	Memory
802728		thimote75	Editor (BOI15_edi)	C++14	100 / 100	71 ms	24644 KiB

edi

#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 (stderr)

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 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37