QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#99441#5526. Jewel of Data Structure Problemswillow#WA 48ms7716kbC++142.2kb2023-04-22 15:38:012023-04-22 15:38:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-22 15:38:02]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:7716kb
  • [2023-04-22 15:38:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, q, a[maxn], ans[maxn], val[maxn];
void Add(int x) {
	for(; x <= n; x += x & -x)
		++ val[x];
}
int Ask(int x) {
	int res = 0;
	for(; x; x -= x & -x)
		res += val[x];
	return res;
}
int cntodd, cnti;
void Mod(int x, int d) {
	if(ans[a[x]] & 1)
		cntodd += d;
	if(x == a[x])
		cnti += d;
}
int sum[maxn << 6], lc[maxn << 6], rc[maxn << 6], rt[maxn], tot;
void Upd(int &o, int l, int r, int p, int d) {
	if(!o)
		o = ++ tot;
	sum[o] += d;
	if(l == r)
		return;
	int mid = (l + r) >> 1;
	if(p <= mid)
		Upd(lc[o], l, mid, p, d);
	else
		Upd(rc[o], mid + 1, r, p, d);
}
int Que(int o, int l, int r, int p) {
	if(!o)
		return 0;
	if(r <= p)
		return sum[o];
	int mid = (l + r) >> 1, ans = 0;
	ans += Que(lc[o], l, mid, p);
	if(p > mid)
		ans += Que(rc[o], mid + 1, r, p);
	return ans;
}
void Update(int x, int v, int d) {
	for(; x <= n; x += x & -x)
		Upd(rt[x], 1, n, v, d);
}
int Query(int x, int v) {
	int ans = 0;
	for(; x; x -= x & -x)
		ans += Que(rt[x], 1, n, v);
	return ans;
}
int main() {
	scanf("%d%d", &n, &q);
	long long all = 0;
	for(int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
		int w = Ask(n) - Ask(a[i]);
		all += w;
		ans[a[i]] += w;
		Add(a[i]);
	}
	memset(val, 0, sizeof val);
	for(int i = n; i; -- i) {
		ans[a[i]] += Ask(a[i]);
		Add(a[i]);
	}
	for(int i = 1; i <= n; ++ i)
		Mod(i, 1), Update(i, a[i], 1);
	for(int u, v; q --; ) {
		scanf("%d%d", &u, &v);
		Mod(u, -1), Mod(v, -1);
		Update(u, a[u], -1), Update(v, a[v], -1);
		swap(a[u], a[v]);
		Update(u, a[u], 1), Update(v, a[v], 1);
		// ans[a[u]] ^= 1, ans[a[v]] ^= 1;
		ans[a[u]] = a[u] - 1 - Query(u, a[u] - 1), ans[a[v]] = a[v] - 1 - Query(v, a[v] - 1);
		Mod(u, 1), Mod(v, 1);
		all ^= 1;
// cerr << all << " " << cnti << " " << cntodd << endl;
// for(int i = 1; i <= n; ++ i)
// 	cerr << a[i] << " ";
// cerr << endl;
// for(int i = 1; i <= n; ++ i)
// 	cerr << ans[i] << " ";
// cerr << endl;
		if(cnti == n) {
			puts("-1");
		}
		else if(all & 1) {
			printf("%d\n", n);
		}
		else if(cntodd) {
			printf("%d\n", n - 1);
		}
		else {
			printf("%d\n", n - 2);
		}
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 6340kb

input:

5 6
2 1 3 4 5
1 2
1 2
1 4
2 1
3 5
1 3

output:

-1
5
4
5
3
5

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 36ms
memory: 6576kb

input:

2 200000
1 2
2 1
2 1
2 1
1 2
1 2
2 1
1 2
2 1
2 1
1 2
2 1
2 1
2 1
2 1
2 1
2 1
1 2
2 1
2 1
1 2
1 2
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 1
1 2
2 1
2 1
2 1
2 1
1 2
1 2
2 1
2 1
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
2 1
1 2
1 2
2 1
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
2 1
1 2
1 2
2 1
1 2
2 1
1 2
2 1
2 1
2 1
2 1...

output:

2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
...

result:

ok 200000 numbers

Test #3:

score: -100
Wrong Answer
time: 48ms
memory: 7716kb

input:

3 200000
2 1 3
2 1
1 3
2 3
2 3
1 3
2 1
2 1
1 3
1 2
3 1
3 1
2 1
1 2
2 1
2 3
2 1
1 3
1 2
1 2
2 3
1 2
2 1
3 2
3 2
1 3
3 2
1 3
2 1
2 1
3 2
2 1
1 3
1 2
1 2
3 1
2 3
2 1
3 2
3 1
1 2
1 2
2 3
1 2
1 2
3 2
3 1
1 2
3 1
1 2
1 3
1 2
2 3
2 3
3 2
2 1
1 3
2 1
3 1
2 1
3 1
3 1
2 3
1 3
2 1
3 2
2 1
3 1
2 3
3 1
2 3
1 3
1...

output:

-1
3
1
3
-1
3
-1
3
2
3
2
3
2
3
1
3
2
3
2
3
-1
3
2
3
1
3
-1
3
-1
3
1
3
-1
3
1
3
2
3
1
3
1
3
2
3
1
3
-1
3
2
3
1
3
1
3
2
3
1
3
-1
3
-1
3
2
3
1
3
2
3
1
3
-1
3
2
3
-1
3
-1
3
-1
3
2
3
-1
3
-1
3
1
3
1
3
1
3
1
3
-1
3
1
3
1
3
1
3
-1
3
-1
3
-1
3
-1
3
2
3
1
3
2
3
1
3
-1
3
-1
3
2
3
-1
3
1
3
1
3
2
3
-1
3
-1
3
1
...

result:

wrong answer 3rd numbers differ - expected: '2', found: '1'