QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#99441 | #5526. Jewel of Data Structure Problems | willow# | WA | 48ms | 7716kb | C++14 | 2.2kb | 2023-04-22 15:38:01 | 2023-04-22 15:38:02 |
Judging History
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'