QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#175007#7108. Couleurmendicillin2#RE 1ms3540kbC++174.2kb2023-09-10 15:33:052023-09-10 15:33:06

Judging History

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

  • [2023-09-10 15:33:06]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3540kb
  • [2023-09-10 15:33:05]
  • 提交

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...

output:


result: