QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#61307 | #2555. Two Bullets | alpha1022 | WA | 6ms | 8480kb | C++14 | 4.9kb | 2022-11-12 08:19:12 | 2022-11-12 08:19:14 |
Judging History
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