QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#83352#5409. Perotationzhouhuanyi0 3ms8008kbC++232.0kb2023-03-01 15:34:512023-03-01 15:34:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-01 15:34:53]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:8008kb
  • [2023-03-01 15:34:51]
  • 提交

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%