QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#83352 | #5409. Perotation | zhouhuanyi | 0 | 3ms | 8008kb | C++23 | 2.0kb | 2023-03-01 15:34:51 | 2023-03-01 15:34:53 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#include<bitset>
#define N 100000
#define M 317
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int lowbit(int x)
{
return x&(-x);
}
int n,q,sz,block[N+1],a[N+1],b[N+1],c[N+1];
bitset<N+1>B[M+1];
bitset<N+1>W[M+1];
bitset<N+1>zero;
bitset<N+1>ans;
void add(int x,int d)
{
for (;x<=n;x+=lowbit(x)) c[x]^=d;
return;
}
int query(int x)
{
int res=0;
for (;x>=1;x-=lowbit(x)) res^=c[x];
return res;
}
bitset<N+1>get(int x)
{
if (!x) return zero;
bitset<N+1>res=W[block[x]-1];
for (int i=(block[x]-1)*sz+1;i<=x;++i) res[n-b[i]+1].flip();
return res;
}
bitset<N+1>calc(int x)
{
if (!x) return zero;
bitset<N+1>res=B[block[x]-1];
for (int i=(block[x]-1)*sz+1;i<=x;++i) res[n-i+1].flip();
return res;
}
int main()
{
int x,y;
bool op,op2;
n=read(),q=read(),sz=sqrt(n);
for (int i=1;i<=n;++i) a[i]=read(),b[a[i]]=i,block[i]=(i-1)/sz+1;
for (int i=1;i<=n;++i) B[block[i]][n-i+1]=W[block[a[i]]][n-i+1]=1;
for (int i=n;i>=1;--i)
{
if (query(a[i])) ans[n-i+1]=1;
add(a[i],1);
}
for (int i=1;i<=block[n];++i) B[i]|=B[i-1],W[i]|=W[i-1];
while (q--)
{
x=read(),y=read();
if (x>y) swap(x,y);
ans^=(get(max(a[x],a[y]))^get(min(a[x],a[y])-1))&(calc(y-1)^calc(x)),op=(get(a[x])&(calc(y-1)^calc(x))).count()&1,op2=(get(a[y])&(calc(y-1)^calc(x))).count()&1;
if (op) ans[n-x+1].flip();
if (op2) ans[n-y+1].flip();
swap(a[x],a[y]),swap(b[a[x]],b[a[y]]);
for (int i=1;i<=block[n];++i) op=W[i][n-x+1],op2=W[i][n-y+1],W[i][n-x+1]=op2,W[i][n-y+1]=op;
op=ans[n-x+1],op2=ans[n-y+1],ans[n-x+1]=op2,ans[n-y+1]=op;
if (a[x]<a[y]) ans[n-y+1].flip();
else ans[n-x+1].flip();
printf("%d\n",(int)(n-ans._Find_first()+2));
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 2ms
memory: 5748kb
input:
2 1 1 2 2 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 3ms
memory: 7816kb
input:
9 7 3 5 8 2 4 9 1 6 7 2 8 3 1 2 1 1 5 3 8 1 3 9 1
output:
7 7 7 7 7 7 7
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 7804kb
input:
7 7 6 7 2 1 5 3 4 3 1 3 1 7 5 1 6 6 5 6 1 1 7
output:
3 4 6 7 4 4 4
result:
ok 7 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 8008kb
input:
7 7 2 4 3 1 5 6 7 7 6 6 3 3 1 1 4 3 4 2 5 4 1
output:
7 6 6 6 6 6 6
result:
ok 7 numbers
Test #5:
score: -10
Wrong Answer
time: 3ms
memory: 5792kb
input:
6 6 5 3 1 4 2 6 5 4 5 2 4 3 6 5 1 5 6 4
output:
-99993 3 4 6 6 6
result:
wrong answer 1st numbers differ - expected: '1', found: '-99993'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%