QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #695365 | #7108. Couleur | Mine_King# | AC ✓ | 883ms | 16184kb | C++14 | 2.6kb | 2024-10-31 19:51:42 | 2024-10-31 19:51:48 |
Judging History
answer
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <set>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;
int T, n, a[100005];
long long b[100005];
struct BIT {
vector<int> w;
void update(int pos, int val) {
for (; pos < (int)w.size(); pos += pos & -pos) w[pos] += val;
return;
}
int query(int pos) {
int res = 0;
for (; pos >= 1; pos -= pos & -pos) res += w[pos];
return res;
}
} tr[100005];
int id[100005];
int l[100005], r[100005];
long long ans[100005];
multiset<long long> s;
void build(int l, int r, int id) {
::l[id] = l, ::r[id] = r;
tr[id].w.clear();
tr[id].w.resize(r - l + 5);
ans[id] = 0;
for (int i = l; i <= r; i++) b[i] = a[i];
sort(b + l, b + r + 1);
for (int i = l; i <= r; i++) {
::id[i] = id;
a[i] = lower_bound(b + l, b + r + 1, a[i]) - b - l + 1;
ans[id] += tr[id].query(r - l + 1) - tr[id].query(a[i]);
tr[id].update(a[i], 1);
}
s.insert(ans[id]);
return;
}
int main() {
scanf("%d", &T);
while (T--) {
s.clear();
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = (long long)a[i] * n + i - 1;
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, (long long)a[i] * n + i - 1) - b;
// for (int i = 1; i <= n; i++) eprintf("%d ", a[i]);
// eputs("");
build(1, n, 1);
for (int i = 1; i <= n; i++) {
printf("%lld ", *prev(s.end()));
int p;
scanf("%d", &p);
p ^= *prev(s.end());
// eprintf("realp: %d\n", p);
int l = ::l[id[p]], r = ::r[id[p]], id = ::id[p];
// eprintf("%d %d %d\n", l, r, id);
s.erase(s.find(ans[id]));
if (p - l < r - p) {
for (int i = l; i <= p; i++) {
tr[id].update(a[i], -1);
ans[id] -= tr[id].query(a[i]);
}
// eprintf("nw: %lld\n", ans[id]);
if (p < r) s.insert(ans[id]);
if (l < p) build(l, p - 1, i + 1);
::l[id] = p + 1;
} else {
for (int i = r; i >= p; i--) {
tr[id].update(a[i], -1);
ans[id] -= tr[id].query(tr[id].w.size() - 1) - tr[id].query(a[i]);
}
// eprintf("nw: %lld\n", ans[id]);
if (l < p) s.insert(ans[id]);
if (p < r) build(p + 1, r, i + 1);
::r[id] = p - 1;
}
}
puts("");
}
return 0;
}
/*
3
5
4 3 1 1 1
5 4 5 3 1
10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10
*/
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8240kb
input:
3 5 4 3 1 1 1 5 4 5 3 1 10 9 7 1 4 7 8 5 7 4 8 21 8 15 5 9 2 4 5 10 6 15 4 8 8 1 12 1 10 14 7 14 2 9 13 10 3 37 19 23 15 7 2 10 15 2 13 4 5 8 7 10
output:
7 0 0 0 0 20 11 7 2 0 0 0 0 0 0 42 31 21 14 14 4 1 1 1 0 0 0 0 0 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 883ms
memory: 16184kb
input:
11116 10 10 5 10 3 6 4 8 5 9 8 31 27 24 11 12 3 0 2 3 1 10 8 2 7 2 8 10 1 10 9 10 6 5 2 13 2 1 0 1 3 1 10 7 10 7 6 1 3 10 6 7 9 21 18 10 1 6 5 4 8 9 10 10 2 10 4 8 8 5 7 2 6 7 20 10 9 1 15 0 4 2 9 7 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 6 3 5 2 7 10 9 1 4 8 10 1 10 1 3...
output:
21 18 16 12 10 6 4 1 1 0 12 12 10 10 4 4 4 2 1 0 20 16 9 5 3 3 3 0 0 0 22 14 8 8 5 5 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 12 7 4 4 2 2 1 0 0 20 18 8 3 1 1 0 0 0 0 45 21 21 10 3 3 3 0 0 0 17 11 8 2 1 1 1 0 0 0 13 4 1 0 0 0 0 0 0 0 29 27 22 15 9 7 4 3 1 0 26 16 9 2 1 1 1 1 1 ...
result:
ok 11116 lines
Extra Test:
score: 0
Extra Test Passed