QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#62265	#2831. Game Theory	microne^#	WA	286ms	35208kb	C++20	3.2kb	2022-11-17 18:48:38	2022-11-17 18:48:42

Judging History

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

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

[2022-11-17 18:48:42]
评测

测评结果：WA
用时：286ms
内存：35208kb

查看

[2022-11-17 18:48:38]
提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct dat
{
	int one,zero,tag,onenum,zeronum;
}tr[1000005<<3];
const long long mod=998244353;
int n,m,a[1000005],one[1000005],zero[1000005];
void update(int p)
{
	tr[p].one=((long long)tr[p<<1].one+tr[p<<1|1].one)%mod;
	tr[p].zero=((long long)tr[p<<1].zero+tr[p<<1|1].zero)%mod;
	tr[p].onenum=tr[p<<1].onenum+tr[p<<1|1].onenum;
	tr[p].zeronum=tr[p<<1].zeronum+tr[p<<1|1].zeronum;
}
void build(int p,int l,int r)
{
	tr[p].tag=0;
	if (l==r)
	{
		tr[p].one=one[l];
		tr[p].zero=zero[r];
		if (tr[p].one!=0) { tr[p].onenum=1; tr[p].zeronum=0; }
		else { tr[p].zeronum=1; tr[p].onenum=0; }
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	update(p);
}
void pushdown(int p)
{
	if (tr[p].tag)
	{
		tr[p].tag=0;
		tr[p<<1].tag^=1;
		tr[p<<1|1].tag^=1;
		swap(tr[p<<1].one,tr[p<<1].zero);
		swap(tr[p<<1|1].one,tr[p<<1|1].zero);
		swap(tr[p<<1].onenum,tr[p<<1].zeronum); 
		swap(tr[p<<1|1].onenum,tr[p<<1|1].zeronum); 
	}
}
void change(int p,int l,int r,int L,int R)
{
	if (l>r) return;
	if (L>R) return;
	if (l==r) { swap(tr[p].one,tr[p].zero); swap(tr[p].onenum,tr[p].zeronum); return; }
	if (l>=L&&r<=R)
	{
		swap(tr[p].one,tr[p].zero);
		swap(tr[p].onenum,tr[p].zeronum);
		tr[p].tag^=1;
		return;	
	}
	pushdown(p);
	int mid=l+r>>1;
	if (L<=mid) change(p<<1,l,mid,L,R);
	if (R>mid) change(p<<1|1,mid+1,r,L,R);
	update(p);
}
struct res
{
	long long one,zero;
};
res ask(int p,int l,int r,int L,int R)
{
	if (l>r) { return {0,0}; }
	if (l==r) { return {tr[p].one,tr[p].zero}; }
	if (l>=L&&r<=R)
	{
		return {tr[p].one,tr[p].zero};
	}
	pushdown(p);
	int mid=l+r>>1;
	res ans={0,0},sum={0,0};
	if (L<=mid) ans=ask(p<<1,l,mid,L,R);
	if (R>mid) sum=ask(p<<1|1,mid+1,r,L,R);
	return {(long long)(ans.one+sum.one)%mod,(long long)(ans.zero+sum.zero)%mod};
}
/*
int query(int p,int l,int r,int L,int R)
{
	if(L<=l&&r<=R) return tr[]
}*/
signed main()
{
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		getchar();
		for (int i=1;i<=n;++i)
		{
			zero[i]=one[i]=0;
		}
		
		for (int i=1;i<=n;++i)
		{
			char ch;
			ch=getchar();
			a[i]=ch-'0';
			if (a[i]==1) one[i]=i;
			if (a[i]==0) zero[i]=i;
		}
		build(1,1,n);
		for (int i=1;i<=m;++i)
		{
			int x,y;
			scanf("%lld%lld",&x,&y);
			change(1,1,n,x,y);
			int k=tr[1].onenum;
			if (k==n) { printf("%lld\n",n); continue; }
			if (k==0) { printf("0\n"); continue; }
			int lzero=ask(1,1,n,1,k).zero;
			int rone=ask(1,1,n,k+1,n).one;
			int ans=((rone-lzero)*2+k)%mod;
			printf("%lld\n",ans);
			/*
			
			if (ask(1,1,n,k,k).zero==k)
			{
				int lzero=ask(1,1,n,1,k-1).zero;
				int rone=ask(1,1,n,k,n).one;
				if (k==n) { printf("%lld\n",n); continue; }
				if (k==0) { printf("0\n"); continue; }
				printf("%lld\n",(rone*2-(2*lzero+k)+mod)%mod);
			}
			else
			{
				int lzero=ask(1,1,n,1,k-1).zero;
				int rone=ask(1,1,n,k+1,n).one;
				if (k==n) { printf("%lld\n",n); continue; }
				if (k==0) { printf("0\n"); continue; }
				printf("%lld\n",(rone*2+k-2*lzero+mod)%mod);
			}
			*/
		}
	}
	return 0;
}
/*
8 7
01011000
1 2
2 6
2 5
1 6
2 6
4 7
1 6
*/

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 9816kb

input:

output:

1
3
5

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 4ms

memory: 9692kb

input:

1 1
0
1 1

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 45ms

memory: 9624kb

input:

output:

result:

ok 200000 lines

Test #4:

score: 0

Accepted

time: 66ms

memory: 9696kb

input:

11 20
00010111000
1 6
1 11
5 6
8 11
1 4
3 8
4 11
1 7
5 9
1 4
6 10
5 6
1 7
5 10
1 10
9 11
6 8
1 4
8 11
1 4
10 20
0101000010
3 4
2 2
4 8
4 6
6 7
3 7
3 3
1 5
1 5
6 8
2 2
2 4
2 6
5 7
1 3
2 5
6 8
7 9
5 8
3 10
4 20
1011
2 4
1 4
1 3
2 3
1 1
2 2
1 2
2 4
1 2
3 4
3 4
3 4
1 4
2 2
1 4
1 3
1 1
1 3
1 3
2 2
4 20
1...

output:

result:

ok 200000 lines

Test #5:

score: 0

Accepted

time: 110ms

memory: 9748kb

input:

11 200
11100010010
2 3
3 7
1 7
3 10
1 3
7 11
2 8
4 8
9 10
9 11
2 7
1 4
9 11
6 7
4 4
8 10
2 6
2 3
1 2
5 7
2 7
1 3
3 4
2 10
9 10
6 11
3 11
3 9
9 10
2 6
5 10
1 8
4 9
6 7
8 11
3 9
7 10
1 9
4 5
5 8
5 7
2 7
6 8
10 10
5 10
7 11
1 11
6 10
2 11
1 4
4 8
6 11
7 10
8 10
4 5
7 10
7 8
4 4
1 6
7 11
3 5
4 9
3 9
8 1...

output:

result:

ok 200000 lines

Test #6:

score: 0

Accepted

time: 154ms

memory: 9812kb

input:

228 2000
111000100100000001001101001100110001011110001110001000101110101100010011011111000001011011000110111010111101011000010010000111111111100011111011011100111010011100111001010011110110011000100100110011111000110001111001010011001010
23 112
24 165
103 162
86 203
99 204
114 217
55 132
168 184
110...

output:

result:

ok 200000 lines

Test #7:

score: 0

Accepted

time: 186ms

memory: 12072kb

input:

20000 20000
110010001110111001001001011110011011011011101011010000011100100100110000011111000010010101001001110101010000011010101110001100111010000101000010110100011111001100001110011011001011010000100110010001000101111101001011100110101111110110100001100100110100000100100001011100111011000101111010...

output:

result:

ok 200000 lines

Test #8:

score: -100

Wrong Answer

time: 286ms

memory: 35208kb

input:

200000 200000
1101110010111101001110011011011100110000111011010010001110010111010000111100010101100111111010010100111110001001011000010110000100111111011110101101011011011101000010000110010011001011101000000100010110001100001010110010011101010100000011101111001110001110110000101101111011111101000101...

output:

result:

wrong answer 2nd lines differ - expected: '994525462', found: '-3718891'