Submission #802769

#	Time	Username	Problem	Language	Result	Execution time	Memory
802769		rnl42	Editor (BOI15_edi)	C++14	100 / 100	69 ms	22300 KiB

edi

#include <bits/stdc++.h>
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

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


int N;
vector<int> level;
vector<int> answer;
vector<int> parent;
struct cmp {
    bool operator()(const int a, const int b) {
        return level[a] < level[b];
    }
};
using PQ = priority_queue<int,vector<int>,cmp>;
PQ cur;
vector<PQ> paquets;

string to_string(PQ pq) {
    vector<int> v;
    while (!pq.empty()) {
        v.push_back(pq.top());
        pq.pop();
    }
    return to_string(v);
}

void merge(PQ &dest, PQ &eaten) {
    if (dest.size() < eaten.size()) dest.swap(eaten);
    while (!eaten.empty()) {
        dest.push(eaten.top());
        eaten.pop();
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> N; level.resize(N+1), answer.resize(N+1);
    paquets.resize(N+1);
    parent.resize(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> level[i];
        if (level[i] >= 0) { answer[i] = level[i]; level[i] = 0; }
        else level[i] *= -1;
    }
    for (int i = N; i >= 1; i--) {
        PQ nxt;
        dbg(i, cur);
        while (!cur.empty() && level[cur.top()] > level[i]) {
            parent[cur.top()] = i;
            merge(nxt, paquets[cur.top()]);
            cur.pop();
        }
        paquets[i].swap(cur);
        cur.swap(nxt);
        cur.push(i);
    }
    for (int i = 1; i <= N; i++) {
        if (level[i]) {
            dbg(i, parent[i]);
            answer[i] = answer[parent[i]-1];
        }
        cout << answer[i] << '\n';
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37