QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#337357#7939. High TowersDays_of_Future_Past#WA 55ms27340kbC++201.4kb2024-02-25 11:04:492024-02-25 11:04:49

Judging History

你现在查看的是最新测评结果

  • [2024-02-25 11:04:49]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:27340kb
  • [2024-02-25 11:04:49]
  • 提交

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