oj.uz

Submission #802769

# Submission time Handle Problem Language Result Execution time Memory
802769 2023-08-02T14:11:10 Z rnl42 Editor (BOI15_edi) C++14
100 / 100
 69 ms 22300 KB 
#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.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 0 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 1 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 57 ms 20068 KB Output is correct
2 Correct 63 ms 20044 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11248 KB Output is correct
2 Correct 32 ms 12984 KB Output is correct
3 Correct 48 ms 15136 KB Output is correct
4 Correct 57 ms 20016 KB Output is correct
5 Correct 61 ms 21048 KB Output is correct
6 Correct 41 ms 19008 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 0 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 1 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 57 ms 20068 KB Output is correct
11 Correct 63 ms 20044 KB Output is correct
12 Correct 28 ms 11248 KB Output is correct
13 Correct 32 ms 12984 KB Output is correct
14 Correct 48 ms 15136 KB Output is correct
15 Correct 57 ms 20016 KB Output is correct
16 Correct 61 ms 21048 KB Output is correct
17 Correct 41 ms 19008 KB Output is correct
18 Correct 69 ms 22300 KB Output is correct
19 Correct 55 ms 22076 KB Output is correct
20 Correct 68 ms 18908 KB Output is correct
21 Correct 61 ms 20044 KB Output is correct
22 Correct 64 ms 20996 KB Output is correct