QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#175007 | #7108. Couleur | mendicillin2# | RE | 1ms | 3540kb | C++17 | 4.2kb | 2023-09-10 15:33:05 | 2023-09-10 15:33:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using ll = int64_t;
using vi = vc<int>;
using pii = pair<int, int>;
using uint = uint32_t;
using ull = uint64_t;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
template <class F>
struct ycr {
F f;
template <class T> explicit ycr(T&& f_) : f(forward<T>(f_)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) {
return f(ref(*this), forward<Args>(args)...);
}
};
template <class F> decltype(auto) yc(F&& f) {
return ycr<decay_t<F>>(forward<F>(f));
}
struct GC {
char buf[1 << 16];
size_t s = 0, e = 0;
char operator()() {
if (s >= e) {
buf[0] = 0;
s = 0;
e = fread(buf, 1, sizeof(buf), stdin);
}
return buf[s++];
}
} gc;
template <class T> T scan_int() {
char c;
while ((c = gc()) < 40);
if (c == '-') return -scan_int<T>();
T a = c - '0';
while (isdigit(c = gc())) a = a * 10 + c - '0';
return a;
}
struct node {
array<int, 2> c;
int v;
};
const int MAXV = 3e6;
node pool[MAXV];
int V;
void reset_pool() {
V = 1;
}
int insert(int a, int l, int r, int k) {
int n = V++;
pool[n] = pool[a];
pool[n].v++;
if (r-l > 1) {
const int m = (l+r)/2;
if (k < m) {
pool[n].c[0] = insert(pool[n].c[0], l, m, k);
} else {
pool[n].c[1] = insert(pool[n].c[1], m, r, k);
}
}
return n;
}
int query(int a, int b, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) {
return 0;
}
if (ql <= l && r <= qr) {
return pool[b].v - pool[a].v;
}
const int m = (l+r)/2;
return query(pool[a].c[0], pool[b].c[0], l, m, ql, qr) +
query(pool[a].c[1], pool[b].c[1], m, r, ql, qr);
}
void solve() {
int N = scan_int<int>();
vector<int> A(N);
for (int i = 0; i < N; i++) {
A[i] = scan_int<int>();
}
reset_pool();
vector<int> roots(N+1);
roots[0] = 0;
for (int i = 0; i < N; i++) {
const int a = A[i];
assert(0 <= a);
assert(a < N);
roots[i+1] = insert(roots[i], 0, N, a);
}
auto query_rect = [&](int xl, int xr, int yl, int yr) -> int {
assert(xl <= xr);
assert(yl <= yr);
if (xl == xr || yl == yr) return 0;
return query(roots[xl], roots[xr], 0, N, yl, yr);
};
set<pair<int, int>> intervals({{0, N}});
vector<ll> cur_num(N);
for (int i = 1; i < N; i++) {
cur_num[0] += query_rect(0, i, A[i]+1, N);
}
multiset<ll> nums;
nums.insert(cur_num[0]);
for (int q = 0; q < N; q++) {
ll cur_ans = *nums.rbegin();
cout << cur_ans << " \n"[q+1==N];
int p;
{
ll p_ = scan_int<ll>();
p = int(p_ ^ cur_ans);
p--;
}
{
auto it = intervals.upper_bound({p, N+1});
assert(it != intervals.begin());
it = prev(it);
assert(it->first <= p);
assert(p < it->second);
const int st_left = it->first;
const int en_left = p;
const int st_right = p+1;
const int en_right = it->second;
intervals.erase(it);
nums.erase(nums.find(cur_num[st_left]));
ll new_num = cur_num[st_left];
// (..., p) and (p, ...)
new_num -= query_rect(st_left, p, A[p]+1, N);
new_num -= query_rect(p+1, en_right, 0, A[p]);
// crossing & one side
ll num_left;
ll num_right;
if (en_left - st_left < en_right - st_right) {
num_left = 0;
for (int i = st_left; i < en_left; i++) {
num_left += query_rect(st_left, i, A[i]+1, N);
new_num -= query_rect(st_right, en_right, 0, A[i]);
}
num_right = new_num - num_left;
} else {
num_right = 0;
for (int i = st_right; i < en_right; i++) {
num_right += query_rect(st_right, i, A[i]+1, N);
new_num -= query_rect(st_left, en_left, A[i]+1, N);
}
num_left = new_num - num_right;
}
assert(num_left >= 0);
assert(num_right >= 0);
if (st_left < en_left) {
cur_num[st_left] = num_left;
nums.insert(num_left);
intervals.emplace(st_left, en_left);
}
if (st_right < en_right) {
cur_num[st_right] = num_right;
nums.insert(num_right);
intervals.emplace(st_right, en_right);
}
}
}
assert(intervals.empty());
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(20);
pool[0].c = {};
pool[0].v = 0;
int T = scan_int<int>();
while (T--) solve();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3540kb
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
Dangerous Syscalls
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...