QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#127278#5409. Perotation1kri0 2ms7844kbC++142.6kb2023-07-19 15:03:482023-07-19 15:03:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 15:03:52]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:7844kb
  • [2023-07-19 15:03:48]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,q,a[100005],x,y;
struct BIT{
	int tree[100005];
	void add(int p,int v){
		while(p<=n)tree[p]+=v,p+=(p&(-p));
		return;
	}
	int ask(int p){
		int ans=0;
		while(p)ans+=tree[p],p-=(p&(-p));
		return ans;
	}
}T[325],_T;
const int B=2;
int B_tot,B_pos[1005],B_id[100005];
int f[100005],_f[100005];
int len[325],val[325][325],ch[325][325];
int cnt[325];
void pushup(int id){
	int l=B_pos[id],r=B_pos[id-1]-1;
	len[id]=0;
	for (int i=r;i>=l;i--){
		f[i]=((T[id-1].ask(a[i])+_T.ask(a[i]))&1);
		_T.add(a[i],1);
	}
	for (int i=r;i>=l;i--)_T.add(a[i],-1);
	for (int i=l;i<=r;i++){
		val[id][++len[id]]=a[i];
		_f[a[i]]=f[i];
	}
	sort(val[id],val[id]+1+len[id]);
	cnt[id]=0;
	for (int i=1;i<=len[id];i++){
		ch[id][i]=(_f[val[id][i]]^_f[val[id][i-1]]);
		if (ch[id][i]==1)cnt[id]++;
	}
	for (int i=l;i<=r;i++)_f[a[i]]=0;
	return;
}
void pushdown(int id){
	int l=B_pos[id],r=B_pos[id-1]-1;
	for (int i=1;i<=len[id];i++)_f[val[id][i]]=(_f[val[id][i-1]]^ch[id][i]);
	for (int i=l;i<=r;i++)f[i]=_f[a[i]];
	for (int i=1;i<=len[id];i++)_f[val[id][i]]=0;
	return;
}
int ge(int id,int x){
	int l=1,r=len[id],ans=len[id]+1;
	while(l<=r){
		int mid=(l+r)/2;
		if (val[id][mid]>=x)ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
int le(int id,int x){
	int l=1,r=len[id],ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if (val[id][mid]<=x)ans=mid,l=mid+1;
		else r=mid-1; 
	}
	return ans;
}
void mdf(int id,int l,int r){
	int pl=ge(id,l),pr=le(id,r);
	if (pl<=len[id]&&pr>=1){
		ch[id][pl]^=1;
		if (ch[id][pl]==0)cnt[id]--;
		else cnt[id]++;
		ch[id][pr+1]^=1;
		if (ch[id][pr+1]==0)cnt[id]--;
		else cnt[id]++;
	}
	return;
}
int main(){
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	B_pos[0]=n+1;
	for (int i=n;i>=1;i--)
		if (i==1||(n-i+1)%B==0)B_pos[++B_tot]=i;
	for (int i=1;i<=B_tot;i++)
		for (int j=B_pos[i];j<B_pos[i-1];j++)B_id[j]=i;
	for (int i=1;i<=B_tot;i++){
		int p=B_pos[i];
		for (int j=n;j>=p;j--)T[i].add(a[j],1);
	}
	for (int i=1;i<=B_tot;i++)pushup(i);
	while(q--){
		scanf("%d%d",&x,&y);
		if (x>y)swap(x,y);
		int l=a[x],r=a[y];
		if (l>r)swap(l,r);
		swap(a[x],a[y]);
		for (int i=1;i<=B_tot;i++){
			int p=B_pos[i];
			if (p>x&&p<=y)T[i].add(a[y],-1),T[i].add(a[x],1);
		}
		for (int i=B_id[y]+1;i<=B_id[x]-1;i++)mdf(i,l,r);
		pushup(B_id[x]);
		if (B_id[x]!=B_id[y])pushup(B_id[y]);
		int ans=n+1;
		for (int i=1;i<=B_tot;i++){
			if (cnt[i]>0)break;
			ans=B_pos[i];
		}
		if (ans>1)pushdown(B_id[ans]+1);
		while(ans>1&&f[ans-1]==0)ans--;
		printf("%d\n",ans);
	}
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 0ms
memory: 7844kb

input:

2 1
1 2
2 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 5720kb

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: 0ms
memory: 5760kb

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: 2ms
memory: 5780kb

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: 0
Accepted
time: 1ms
memory: 5912kb

input:

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

output:

1
3
4
6
6
6

result:

ok 6 numbers

Test #6:

score: 0
Accepted
time: 2ms
memory: 5724kb

input:

10 9
7 9 2 5 1 6 8 3 4 10
4 5
2 9
10 6
6 1
5 3
10 1
5 7
1 7
8 3

output:

4
8
10
10
10
8
6
8
8

result:

ok 9 numbers

Test #7:

score: 0
Accepted
time: 0ms
memory: 5708kb

input:

8 8
4 2 6 5 8 3 7 1
5 6
2 4
6 5
6 1
4 6
1 2
2 8
8 6

output:

8
8
8
8
8
8
8
8

result:

ok 8 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 5712kb

input:

8 8
6 8 4 7 1 3 5 2
1 4
3 8
3 8
8 3
6 2
1 5
1 6
7 4

output:

8
8
8
8
8
8
8
8

result:

ok 8 numbers

Test #9:

score: -10
Wrong Answer
time: 0ms
memory: 5824kb

input:

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

output:

5
2
3
5
3
2
3
2

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%