QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#108658	#5526. Jewel of Data Structure Problems	LG_Monkey	TL	2ms	3312kb	C++14	1.1kb	2023-05-25 22:16:36	2023-05-25 22:16:39

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-25 22:16:39]
评测

测评结果：TL
用时：2ms
内存：3312kb

查看

[2023-05-25 22:16:36]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second 
#define deb(var) cerr << #var << '=' << (var) << "; "
#define int long long
int n, q, a[200010];
int cnt[2];
int w[200010];
void add(int p, int x) {
	for (int i = p; i <= n; i += i & (-i)) w[i] += x;
}
int qry(int p) {
	int res = 0;
	for (int i = p; i; i -= i & (-i)) res += w[i];
	return res;
}
int rev = 0, flg = 0;
void rem(int p) {
	flg -= a[p] == p;
	cnt[(a[p] + 10000000 - p) & 1]--; 
}
void upd(int p) {
	flg += a[p] == p;
	cnt[(a[p] + 10000000 - p) & 1]++; 
}
signed main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		flg += a[i] == i;
		cnt[(a[i] + 10000000 - i) & 1]++;
		rev += qry(n) - qry(a[i]); add(a[i], 1);
	}
	rev &= 1;
	while (q--) {
		int u, v;
		cin >> u >> v;
		rem(u); rem(v);
		swap(a[u], a[v]);
		upd(u); upd(v);
		rev ^= 1;
		if (rev) {
			cout << n << "\n";
		} else {
			if (cnt[1]) {
				cout << n - 1 << "\n";
			} else {
				if (flg == n) cout << "-1\n";
				else {
					cout << n - 2 << "\n";
				}
			}
		}
	}
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 3312kb

input:

output:

result:

ok 6 numbers

Test #2:

score: -100

Time Limit Exceeded

input:

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