QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#61307#2555. Two Bulletsalpha1022WA 6ms8480kbC++144.9kb2022-11-12 08:19:122022-11-12 08:19:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-12 08:19:14]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:8480kb
  • [2022-11-12 08:19:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const int N = 1e5;

int n, p[N + 5], q[N + 5];
int level[N + 5], outd[N + 5];
int a[N + 5], b[N + 5];

struct BinaryIndexedTree {
  int c0[N + 5], c1[N + 5];
  void update(int x, int k) {
    for (; x <= n; x += x & -x) ++c0[x], c1[x] = max(c1[x], k);
  }
  pair<int, int> query(int x) {
    int ret0 = 0, ret1 = 0;
    for (; x; x &= x - 1) ret0 += c0[x], ret1 = max(ret1, c1[x]);
    return {ret0, ret1};
  }
} bit;

struct TreeOfTree {
  struct segnode {
    int max;
    int ls, rs;
  } seg[N * 80 + 5];
  void insert(int x, int k, int &u, int tl, int tr) {
    static int tot = 0;
    if (!u) u = ++tot;
    seg[u].max = max(seg[u].max, k);
    if (tl == tr) return ;
    int mid = (tl + tr) >> 1;
    if (x <= mid) insert(x, k, seg[u].ls, tl, mid);
    else insert(x, k, seg[u].rs, mid + 1, tr);
  }
  int query(int l, int r, int u, int tl, int tr) {
    if (!u || (l <= tl && tr <= r)) return seg[u].max;
    int mid = (tl + tr) >> 1;
    int ret = 0;
    if (l <= mid) ret = max(ret, query(l, r, seg[u].ls, tl, mid));
    if (r > mid) ret = max(ret, query(l, r, seg[u].rs, mid + 1, tr));
    return ret;
  }
  #define ls (u << 1)
  #define rs (ls | 1)
  int rt[N * 4 + 5];
  void insert(int x, int y, int k, int u, int tl, int tr) {
    insert(y, k, rt[u], 1, n);
    if (tl == tr) return ;
    int mid = (tl + tr) >> 1;
    if (x <= mid) insert(x, y, k, ls, tl, mid);
    else insert(x, y, k, rs, mid + 1, tr);
  }
  void insert(int x, int y, int k) { insert(x, y, k, 1, 1, n); }
  int query(int l, int r, int x, int y, int u, int tl, int tr) {
    if (l <= tl && tr <= r) return query(x, y, rt[u], 1, n);
    int mid = (tl + tr) >> 1;
    int ret = 0;
    if (l <= mid) ret = max(ret, query(l, r, x, y, ls, tl, mid));
    if (r > mid) ret = max(ret, query(l, r, x, y, rs, mid + 1, tr));
    return ret;
  }
  int query(int l, int r, int x, int y) { return l <= r && x <= y ? query(l, r, x, y, 1, 1, n) : 0; }
  #undef ls
  #undef rs
} tr;

struct SegmentTree {
  #define ls (u << 1)
  #define rs (ls | 1)
  struct node {
    pair<int, int> val;
    int tag;
  } seg[N * 4 + 5];
  void build(int u, int tl, int tr) {
    if (tl == tr) { seg[u].val = make_pair(outd[q[tl]], q[tl]); return ; }
    int mid = (tl + tr) >> 1;
    build(ls, tl, mid), build(rs, mid + 1, tr);
    seg[u].val = min(seg[ls].val, seg[rs].val);
  }
  void build() { build(1, 1, n); }
  void pushDown(int u) {
    if (seg[u].tag) {
      seg[ls].val.first += seg[u].tag, seg[ls].tag += seg[u].tag;
      seg[rs].val.first += seg[u].tag, seg[rs].tag += seg[u].tag;
      seg[u].tag = 0;
    }
  }
  void erase(int x, int u, int tl, int tr) {
    if (tl == tr) { seg[u].val = make_pair(inf, q[tl]); return ; }
    pushDown(u);
    int mid = (tl + tr) >> 1;
    if (x <= mid) erase(x, ls, tl, mid);
    else erase(x, rs, mid + 1, tr);
    seg[u].val = min(seg[ls].val, seg[rs].val);
  }
  void erase(int x) { erase(x, 1, 1, n); }
  void update(int l, int r, int k, int u, int tl, int tr) {
    if (l <= tl && tr <= r) {
      seg[u].val.first += k, seg[u].tag += k;
      return ;
    }
    pushDown(u);
    int mid = (tl + tr) >> 1;
    if (l <= mid) update(l, r, k, ls, tl, mid);
    if (r > mid) update(l, r, k, rs, mid + 1, tr);
    seg[u].val = min(seg[ls].val, seg[rs].val);
  }
  void update(int l, int r, int k) { if (l <= r) update(l, r, k, 1, 1, n); }
  pair<int, int> query() { return seg[1].val; }
  #undef ls
  #undef rs
} seg;

vector<pair<int, int>> ans;
priority_queue<int> que;

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", p + i), q[p[i]] = i;
  for (int i = n; i; --i) {
    auto res = bit.query(p[i] - 1);
    outd[i] = res.first, bit.update(p[i], (level[i] = res.second) + 1);
  }
  iota(a + 1, a + n + 1, 1), sort(a + 1, a + n + 1, [](int x, int y) { return level[x] > level[y]; });
  for (int l = 1, r; l <= n; l = r + 1) {
    for (r = l; r < n && level[a[r + 1]] == level[a[l]]; ++r);
    sort(a + l, a + r + 1, [](int x, int y) {
      bool flag = 0;
      if (x > y) flag = 1, swap(x, y);
      return (tr.query(1, x - 1, p[x] + 1, p[y]) < tr.query(x + 1, y - 1, p[y] + 1, n)) ^ flag;
    });
    for (int i = l; i <= r; ++i) tr.insert(a[i], p[a[i]], i);
  }
  for (int i = 1; i <= n; ++i) b[a[i]] = i;
  seg.build();
  for (int i = 1; i <= n; ++i) if (!outd[a[i]]) que.push(i), seg.erase(p[a[i]]);
  while (!que.empty()) {
    int x = que.top(); que.pop(), seg.update(p[a[x]] + 1, n, -1);
    int y = x;
    if (!que.empty()) y = que.top(), que.pop(), seg.update(p[a[y]] + 1, n, -1);
    for (auto res = seg.query(); res.first <= 0; res = seg.query())
      que.push(b[res.second]), seg.erase(p[res.second]);
    ans.emplace_back(p[a[x]], p[a[y]]);
  }
  reverse(ans.begin(), ans.end());
  printf("%d\n", ans.size());
  for (auto i: ans) printf("%d %d\n", i.first, i.second);
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 8324kb

input:

8
4 3 8 2 1 7 6 5

output:

4
4 8
3 7
2 6
1 5

result:

ok da

Test #2:

score: 0
Accepted
time: 5ms
memory: 8340kb

input:

8
5 6 7 1 2 8 3 4

output:

4
7 8
5 6
1 2
3 4

result:

ok da

Test #3:

score: 0
Accepted
time: 1ms
memory: 8268kb

input:

4
1 2 4 3

output:

2
2 4
3 1

result:

ok da

Test #4:

score: 0
Accepted
time: 5ms
memory: 8268kb

input:

2
1 2

output:

1
1 2

result:

ok da

Test #5:

score: 0
Accepted
time: 2ms
memory: 8328kb

input:

2
2 1

output:

2
2 2
1 1

result:

ok da

Test #6:

score: 0
Accepted
time: 2ms
memory: 8320kb

input:

3
1 2 3

output:

2
3 3
1 2

result:

ok da

Test #7:

score: 0
Accepted
time: 2ms
memory: 8324kb

input:

3
1 3 2

output:

2
3 3
2 1

result:

ok da

Test #8:

score: 0
Accepted
time: 5ms
memory: 8260kb

input:

3
2 1 3

output:

2
2 2
1 3

result:

ok da

Test #9:

score: 0
Accepted
time: 4ms
memory: 8404kb

input:

3
2 3 1

output:

2
2 3
1 1

result:

ok da

Test #10:

score: 0
Accepted
time: 2ms
memory: 8372kb

input:

3
3 1 2

output:

2
3 3
1 2

result:

ok da

Test #11:

score: 0
Accepted
time: 5ms
memory: 8284kb

input:

3
3 2 1

output:

3
3 3
2 2
1 1

result:

ok da

Test #12:

score: 0
Accepted
time: 1ms
memory: 8336kb

input:

4
1 2 3 4

output:

2
3 4
1 2

result:

ok da

Test #13:

score: 0
Accepted
time: 2ms
memory: 8480kb

input:

4
1 2 4 3

output:

2
2 4
3 1

result:

ok da

Test #14:

score: 0
Accepted
time: 1ms
memory: 8440kb

input:

4
1 3 2 4

output:

2
4 3
2 1

result:

ok da

Test #15:

score: 0
Accepted
time: 5ms
memory: 8292kb

input:

4
1 3 4 2

output:

2
3 4
2 1

result:

ok da

Test #16:

score: 0
Accepted
time: 5ms
memory: 8480kb

input:

4
1 4 2 3

output:

2
1 4
2 3

result:

ok da

Test #17:

score: -100
Wrong Answer
time: 2ms
memory: 8224kb

input:

4
1 4 3 2

output:

2
3 4
2 1

result:

FAIL removed all buildings