QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#163518 | #7108. Couleur | luanmenglei | RE | 2ms | 5464kb | C++17 | 3.3kb | 2023-09-04 09:58:58 | 2023-09-04 09:58:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void debug(const char *msg, ...) {
#ifdef CLESIP
va_list args;
va_start(args, msg);
static char res[512];
vsprintf(res, msg, args);
cerr << "[DEBUG] " << res << "\n";
va_end(args);
#endif
}
using i64 = long long;
const int N = 1e5 + 10;
const int SEG_SIZE = N * 80;
int n, a[N], cnt, rt[N], p[N];
map<int, int> seg;
multiset<i64> ans;
struct Node {
int cnt, tag, lc, rc, min, max;
i64 sum;
} t[SEG_SIZE];
void pull(int x) {
t[x].sum = 0, t[x].cnt = 0, t[x].min = n + 1, t[x].max = 0;
if (t[x].lc) t[x].sum += t[t[x].lc].sum, t[x].cnt += t[t[x].lc].cnt, t[x].min = min(t[t[x].lc].min, t[x].min), t[x].max = max(t[t[x].lc].max, t[x].max);
if (t[x].rc) t[x].sum += t[t[x].rc].sum, t[x].cnt += t[t[x].rc].cnt, t[x].min = min(t[t[x].rc].min, t[x].min), t[x].max = max(t[t[x].rc].max, t[x].max);
}
void apply(int x, int k) { t[x].sum += 1LL * t[x].cnt * k, t[x].tag += k; }
void push(int x) {
if (t[x].tag) {
if (t[x].lc) apply(t[x].lc, t[x].tag);
if (t[x].rc) apply(t[x].rc, t[x].tag);
t[x].tag = 0;
}
}
void add(int &x, int l, int r, int v, int p, int sum) {
if (!x) t[x = ++ cnt] = { 0, 0, 0, 0, n + 1, 0, 0 };
if (l == r) {
t[x] = { 1, 0, 0, 0, p, p, sum };
return;
}
int mid = (l + r) >> 1;
if (v <= mid) add(t[x].lc, l, mid, v, p, (t[x].rc ? t[t[x].rc].cnt : 0) + sum);
else add(t[x].rc, mid + 1, r, v, p, sum);
pull(x);
}
void extract(int &x, int &y, int k) {
if (!y) return;
// debug("min: %d max: %d cnt: %d", t[y].min, t[y].max, t[y].cnt);
if (t[y].max <= k) {
x = y;
y = 0;
return;
}
if (t[y].min > k) {
x = 0;
return;
}
push(y);
t[x = ++ cnt] = { 0, 0, 0, 0, n + 1, 0, 0 };
extract(t[x].lc, t[y].lc, k);
extract(t[x].rc, t[y].rc, k);
apply(t[y].lc, -t[t[x].rc].cnt);
pull(x), pull(y);
}
void solve() {
// debug("new test case");
seg.clear(), ans.clear(), cnt = 0;
cin >> n;
for (int i = 1; i <= n; i ++) rt[i] = 0;
for (int i = 1; i <= n; i ++) cin >> a[i], p[i] = i;
sort(p + 1, p + 1 + n, [&](int x, int y) { return a[x] == a[y] ? x < y : a[x] < a[y]; });
for (int i = 1; i <= n; i ++) a[p[i]] = i;
// for (int i = 1; i <= n; i ++) debug("a[%d] = %d", i, a[i]);
for (int i = 1; i <= n; i ++)
add(rt[1], 1, n, a[i], i, 0);
seg[1] = n, ans.insert(t[rt[1]].sum);
// debug("sum: %d", t[rt[1]].sum);
cout << t[rt[1]].sum << " ";
int q = n, lst = t[rt[1]].sum;
for (int i = 1; i <= q; i ++) {
int p; cin >> p;
p ^= lst;
if (i == q) break;
auto iter = prev(seg.upper_bound(p));
auto [l, r] = *iter;
seg.erase(iter);
r += l - 1;
// debug("p: %d l: %d r: %d", p, l, r);
int rtl = 0, rtr = rt[l], tmp;
ans.extract(t[rt[l]].sum);
// debug("ans size: %d", ans.size());
rt[l] = 0;
extract(rtl, rtr, p - 1);
extract(tmp, rtr, p);
if (l <= p - 1) {
// debug("left cnt: %d", t[rt[l]].cnt);
rt[l] = rtl;
seg[l] = p;
ans.insert(t[rt[l]].sum);
}
if (p + 1 <= r) {
// debug("right cnt: %d", t[rt[p + 1]].cnt);
rt[p + 1] = rtr;
seg[p + 1] = r;
ans.insert(t[rt[p + 1]].sum);
}
cout << (lst = *prev(ans.end())) << " \n"[i + 1 == q];
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int tt; cin >> tt;
while (tt --) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5464kb
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: -100
Runtime Error
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 0 0 0 0 0 0 ...