QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#161442#7108. Couleurucup-team1196#AC ✓3099ms54320kbC++234.1kb2023-09-02 23:57:022023-09-02 23:57:02

Judging History

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

  • [2023-09-02 23:57:02]
  • 评测
  • 测评结果：AC
  • 用时：3099ms
  • 内存：54320kb
查看
  • [2023-09-02 23:57:02]
  • 提交

answer

/*

                                _/                                      _/
       _/_/        _/_/_/      _/_/_/        _/_/_/      _/  _/_/               _/_/_/
    _/    _/    _/            _/    _/    _/    _/      _/_/          _/       _/    _/
   _/    _/    _/            _/    _/    _/    _/      _/            _/       _/    _/
    _/_/        _/_/_/      _/    _/      _/_/_/      _/            _/       _/    _/

*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<utility>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<ctime>
#include<functional>
#include<bitset>
#define P pair<int,int>
#define ll long long
#define ull unsigned long long
#define lson id*2,l,mid
#define rson id*2+1,mid+1,r
#define ls id*2
#define rs (id*2+1)
#define Mod(a,b) a<b?a:a%b+b
#define cl0(a) memset(a,0,sizeof(a))
#define cl1(a) memset(a,-1,sizeof(a))
using namespace std;

const ll M = 1e9 + 7;
const ll INF = 1e9;
const int N = 410;
const double _e = 10e-6;
const int maxn = 1e5 + 10;
const int matSize = 9;
const int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
const int _dx[8] = { -1,-1,-1,0,0,1,1,1 }, _dy[8] = { -1,0,1,-1,1,-1,0,1 };

int x, y;
int n, m;

int c[maxn];
map<int, ll> mp;
set<int> s; multiset<ll> ms;
struct chairtree { int l, r; ll cnt; }t[maxn << 5];
int root[maxn], a[maxn];
int lens, tot;

int build(int l, int r)
{
	int id = ++tot;
	t[id].cnt = 0;
	if (l == r) return id;
	int mid = (l + r) / 2;
	t[id].l = build(l, mid); t[id].r = build(mid + 1, r);
	return id;
}
int update(int id, int l, int r, int x)
{
	int now = ++tot;
	t[now].cnt = t[id].cnt + 1;
	if (l == r)
		return now;
	int mid = (l + r) / 2;
	if (x <= mid) {
		t[now].r = t[id].r;
		t[now].l = update(t[id].l, l, mid, x);
	}
	else {
		t[now].l = t[id].l;
		t[now].r = update(t[id].r, mid + 1, r, x);
	}
	return now;
}
ll query(int lid, int rid, int l, int r, int _l, int _r)
{
	if (l == _l&&r == _r)
		return t[rid].cnt - t[lid].cnt;
	int mid = (l + r) / 2;
	if (_r <= mid)
		return query(t[lid].l, t[rid].l, l, mid, _l, _r);
	else if (_l > mid)
		return query(t[lid].r, t[rid].r, mid + 1, r, _l, _r);
	else
		return query(t[lid].l, t[rid].l, l, mid, _l, mid) + query(t[lid].r, t[rid].r, mid + 1, r, mid + 1, _r);
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		ll ans = 0; tot = 0; lens = n + 1;
		mp.clear(); s.clear(); ms.clear();
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++)
			scanf("%d", &c[i]);
		root[0] = build(1, lens);
		for (int i = 1; i <= n; i++) {
			ans += query(root[0], root[i - 1], 1, lens, a[i] + 1, lens);
			root[i] = update(root[i - 1], 1, lens, a[i]);
		}
		s.insert(0); s.insert(lens); ms.insert(ans); mp[0] = ans;
		for (int i = 1; i < n; i++) {
			printf("%lld ", ans);
			if (ans == 0)continue;
			int del = c[i] ^ ans;
			auto it = s.upper_bound(del);
			int l, r = *it; it--; l = *it;
			ll lcnt, rcnt, temp = 0;
			if (del - l <= r - del) {
				lcnt = 0, rcnt = mp[l]; ms.erase(ms.lower_bound(rcnt));
				for (int j = l + 1; j < del; j++) {
					if (a[j] > 1) {
						temp += query(root[j], root[del - 1], 1, lens, 1, a[j] - 1);
						rcnt -= query(root[del - 1], root[r - 1], 1, lens, 1, a[j] - 1);
					}
				}
				lcnt += temp; rcnt -= temp;
				if (a[del] > 1)
					rcnt -= query(root[del], root[r - 1], 1, lens, 1, a[del] - 1);
			}
			else {
				lcnt = mp[l], rcnt = 0; ms.erase(ms.lower_bound(lcnt));
				for (int j = del + 1; j < r; j++) {
					temp += query(root[del], root[j - 1], 1, lens, a[j] + 1, lens);
					lcnt -= query(root[l], root[del], 1, lens, a[j] + 1, lens);
				}
				lcnt -= temp; rcnt += temp;
				lcnt -= query(root[l], root[del - 1], 1, lens, a[del] + 1, lens);
			}
			ms.insert(lcnt); ms.insert(rcnt);
			mp[l] = lcnt; mp[del] = rcnt;
			auto itt = ms.end(); itt--; ans = *itt;
			s.insert(del);
		}
		printf("%lld\n", ans);
	}
	return 0;
}
源文件, 语言: C++23

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5928kb

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: 3099ms
memory: 54320kb

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

result:

ok 11116 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2024-12-03 04:00:55 | 开源项目