QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#337357 | #7939. High Towers | Days_of_Future_Past# | WA | 55ms | 27340kb | C++20 | 1.4kb | 2024-02-25 11:04:49 | 2024-02-25 11:04:49 |
Judging History
answer
#include <bits/stdc++.h>
#define SZ(c) ((int)(c).size())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int N = 5e5+10;
int n, a[N];
pii lmx[N << 2], rmx[N << 2];
void init(int i, int l, int r) {
if (l == r) {
lmx[i] = pii(a[l], -l);
rmx[i] = pii(a[l], l);
return;
}
int mid = (l + r) / 2;
init(i * 2, l, mid);
init(i * 2 + 1, mid+1, r);
lmx[i] = max(lmx[i*2], lmx[i*2+1]);
rmx[i] = max(rmx[i*2], rmx[i*2+1]);
}
void qry(int i, int l, int r, int qa, int qb, pii &qlmx, pii &qrmx) {
if (qa <= l && r <= qb) {
qlmx = max(qlmx, lmx[i]);
qrmx = max(qrmx, rmx[i]);
return;
}
if (qb < l || r < qa) {
return;
}
int mid = (l + r) / 2;
qry(i * 2, l, mid, qa, qb, qlmx, qrmx);
qry(i * 2 + 1, mid+1, r, qa, qb, qlmx, qrmx);
}
int cur;
int h[N];
void dfs(int l, int r) {
if (l > r)
return;
pii qlmx{0, 0};
pii qrmx{0, 0};
qry(1, 1, n, l, r, qlmx, qrmx);
if (qlmx.second == -l) {
h[l] = cur;
--cur;
dfs(l + 1, r);
} else {
h[qrmx.second] = cur;
--cur;
dfs(l, qrmx.second - 1);
dfs(qrmx.second + 1, r);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a+i);
}
init(1, 1, n);
cur = n;
dfs(1, n);
for (int i = 1; i <= n; ++i)
printf("%d%c", h[i], " \n"[i == n]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10052kb
input:
6 3 3 4 2 5 1
output:
4 3 5 2 6 1
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 10072kb
input:
4 3 3 3 3
output:
4 3 2 1
result:
ok
Test #3:
score: -100
Wrong Answer
time: 55ms
memory: 27340kb
input:
264668 5 5 5 5 9 5 5 5 7 3 5 3 11 9 9 9 8 9 8 9 12 4 4 9 5 5 6 4 12 4 7 5 6 5 18 12 6 12 11 11 11 11 11 11 12 19 5 5 8 6 6 6 26 7 7 7 8 6 7 6 6 12 10 6 9 8 8 8 10 4 22 4 4 6 3 6 4 4 8 5 5 5 7 3 8 6 6 6 6 8 3 5 3 6 4 4 8 5 5 5 10 6 6 6 6 17 4 12 5 11 6 10 7 9 8 8 16 5 5 5 8 4 4 12 8 7 7 8 6 9 4 14 5 ...
output:
264651 264650 264649 264648 264652 264646 264645 264644 264647 264642 264643 264641 264653 264640 264639 264638 264635 264636 264634 264637 264654 264632 264631 264633 264629 264628 264630 264627 264655 264625 264626 264623 264624 264622 264656 264621 264618 264619 264617 264616 264615 264614 264613...
result:
wrong answer