QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#63931#2831. Game Theorypty6666WA 296ms27968kbC++143.6kb2022-11-23 18:31:292022-11-23 18:31:32

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-23 18:31:32]
  • 评测
  • 测评结果：WA
  • 用时：296ms
  • 内存：27968kb
查看
  • [2022-11-23 18:31:29]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <random>
#include <ctime>
#include <string>
#define lson ( p << 1 )
#define rson ( p << 1 | 1 )
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
struct Tree{
	ll val[2][2];
	int lazy;
	int cnt[2];
}tree[maxn << 2];
int n,q;
string s;

Tree combine(Tree x,Tree y)
{
	Tree ret{};
	for(int i = 0;i<=1;i++){
		for(int j = 0;j<=1;j++){
			ret.val[i][j] = x.val[i][j] + y.val[i][j];
		}
		ret.cnt[i] = x.cnt[i] + y.cnt[i];
	}
	return ret;
}

void pushdown(int p)
{
	swap(tree[lson].val[0][0],tree[lson].val[1][0]);
	swap(tree[lson].val[0][1],tree[lson].val[1][1]);
	swap(tree[rson].val[0][0],tree[rson].val[1][0]);
	swap(tree[rson].val[0][1],tree[rson].val[1][1]);
	swap(tree[lson].cnt[0],tree[lson].cnt[1]);
	swap(tree[rson].cnt[0],tree[rson].cnt[1]);
	tree[lson].lazy ^= 1;
	tree[rson].lazy ^= 1;
	tree[p].lazy = 0;
}

void build(int l = 1,int r = n,int p = 1)
{
	tree[p].lazy = 0;
	if(l == r){
		for(int i =0;i<=1;i++){
			for(int j = 0;j<=1;j++){
				tree[p].val[i][j] = 0;
			}
			tree[p].cnt[i] = 0;
		}
		if(s[l] == '0'){
			tree[p].val[0][0] = l;
			tree[p].val[0][1] = n - l + 1;
			tree[p].cnt[0] = 1;
		}
		else {
			tree[p].val[1][0] = l;
			tree[p].val[1][1] = n - l + 1;
			tree[p].cnt[1] = 1;
		}
		return;
	}
	int mid = (l + r) >> 1;
	build(l,mid,lson);
	build(mid + 1,r,rson);
	for(int i = 0;i<=1;i++){
		for(int j = 0;j<=1;j++){
			tree[p].val[i][j] = tree[lson].val[i][j] + tree[rson].val[i][j];
		}
		tree[p].cnt[i] = tree[lson].cnt[i] + tree[rson].cnt[i];
	}
}

void update(int s,int t,int l = 1,int r = n,int p = 1)
{
	if(s <= l && r <= t){
		tree[p].lazy ^= 1;
		swap(tree[p].val[0][0],tree[p].val[1][0]);
		swap(tree[p].val[0][1],tree[p].val[1][1]);
		swap(tree[p].cnt[0],tree[p].cnt[1]);
		return;
	}
	int mid = (l + r) >> 1;
	if(tree[p].lazy)
		pushdown(p);
	if(s <= mid)
		update(s,t,l,mid,lson);
	if(t > mid)
		update(s,t,mid + 1,r,rson);
	for(int i = 0;i<=1;i++){
		for(int j = 0;j<=1;j++){
			tree[p].val[i][j] = tree[lson].val[i][j] + tree[rson].val[i][j];
		}
		tree[p].cnt[i] = tree[lson].cnt[i] + tree[rson].cnt[i];
	}
}

Tree query(int s,int t,int l = 1,int r = n,int p = 1)
{
	if(s <= l && r <= t){
		return tree[p];
	}
	if(tree[p].lazy)
		pushdown(p);
	int mid = ( l + r) >> 1;
	if(s <= mid && t > mid)
		return combine(query(s,t,l,mid,lson), query(s,t,mid + 1,r,rson));
	else if(s <= mid)
		return query(s,t,l,mid,lson);
	else return query(s,t,mid + 1,r,rson);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	while(cin >> n >> q){
		cin >> s;
		s = " " + s;
		build();
		for(int i = 1;i<=q;i++){
			int l,r;
			cin >> l >> r;
			update(l,r);
			Tree temp = query(1,n);
			int k = temp.cnt[1];
			if(k == 0){
				cout << 0 << "\n";
				continue;
			}
			Tree tt = query(k,k);
			ll ans = 0;
			if(tt.cnt[1] == 1) {
				Tree temp1 {};
				if ( k - 1 >= 1 )
					temp1 = query( 1, k - 1 );
				Tree temp2 = query(k,n);
				ans += temp2.val[1][0] - temp1.val[0][0];
				temp2 = {};
				if(k + 1 <= n)
					temp2 = query(k + 1,n);
				ans += temp1.val[0][1] - temp2.val[1][1];
				cout << ans << "\n";
			}
			else {
				Tree temp1 = query( 1, k );
				Tree temp2{};
				if(k + 1 <= n){
					temp2 = query(k + 1,n);
				}
				ans += temp1.val[0][1] - temp2.val[1][1];
				temp1 = {};
				if(k - 1 >= 1)
					temp1 = query(1,k - 1);
				ans += temp2.val[1][0] - temp1.val[0][0];
				cout << ans << "\n";
			}
		}
	}
	return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3200kb

input:

3 2
010
1 2
2 3
5 1
00000
1 5

output:

1
3
5

result:

ok 3 lines

Test #2:

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

input:

1 1
0
1 1

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 51ms
memory: 3204kb

input:

2 2
01
2 2
2 2
2 2
01
1 2
1 2
1 2
1
1 1
1 1
1 2
1
1 1
1 1
2 2
00
1 2
1 2
2 2
11
1 2
1 2
2 2
01
2 2
1 1
2 2
10
2 2
1 2
2 2
01
1 2
1 2
1 2
0
1 1
1 1
2 2
01
1 2
2 2
1 2
0
1 1
1 1
1 2
1
1 1
1 1
2 2
10
1 2
1 1
1 2
0
1 1
1 1
2 2
01
1 2
1 2
2 2
10
1 2
1 1
1 2
0
1 1
1 1
1 2
0
1 1
1 1
1 2
1
1 1
1 1
2 2
10
1 ...

output:

0
3
1
3
0
1
0
1
2
0
0
2
0
1
2
0
1
3
1
0
1
2
1
0
0
1
3
2
1
0
1
3
3
2
1
0
1
0
0
1
0
1
0
2
2
1
0
1
2
1
1
0
2
0
2
3
1
0
0
1
2
0
0
1
0
1
0
1
1
0
1
2
2
0
0
2
0
1
0
1
1
0
1
0
1
0
0
1
0
1
0
1
2
0
3
0
1
0
0
1
1
0
1
0
1
2
0
2
1
0
0
3
1
2
0
1
3
2
1
0
0
1
2
0
2
0
0
1
0
1
1
0
1
0
1
0
1
0
1
2
1
0
3
1
0
3
0
1
0
1
...

result:

ok 200000 lines

Test #4:

score: 0
Accepted
time: 64ms
memory: 3248kb

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:

16
55
53
25
13
15
43
52
41
33
34
40
43
45
35
28
25
33
45
37
19
20
35
38
36
41
36
29
36
29
22
31
20
23
28
20
21
10
14
30
2
10
5
7
10
9
7
2
0
10
0
10
2
1
9
6
7
4
7
8
4
9
1
6
8
3
5
7
3
7
6
8
6
9
6
7
2
0
5
3
66
105
83
68
92
137
92
76
85
92
127
120
119
104
124
65
70
88
61
53
40
43
25
21
32
59
67
32
29
50...

result:

ok 200000 lines

Test #5:

score: 0
Accepted
time: 103ms
memory: 3308kb

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:

27
22
29
25
30
39
34
17
15
12
18
22
33
35
40
45
54
36
34
37
39
52
54
37
39
33
40
51
37
46
52
24
26
24
16
7
35
30
32
40
39
37
28
15
41
28
39
4
26
54
49
31
39
26
28
44
46
41
35
26
17
31
24
28
30
22
38
13
18
60
38
36
49
41
41
43
27
28
54
41
14
16
7
8
20
22
45
26
27
20
21
12
27
31
28
21
39
37
39
30
31
2...

result:

ok 200000 lines

Test #6:

score: 0
Accepted
time: 155ms
memory: 3424kb

input:

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

output:

13974
13044
13700
13434
14000
13220
13546
13913
13184
13533
13051
13689
13533
14119
14470
13742
13980
13022
13167
13648
13592
13159
13028
13041
12964
12996
12792
12539
12039
11974
12336
12742
12841
12831
12730
12004
12065
12352
13037
11923
12332
14242
13475
13935
13121
12996
12755
13353
13720
13043
...

result:

ok 200000 lines

Test #7:

score: 0
Accepted
time: 237ms
memory: 7296kb

input:

20000 20000
110010001110111001001001011110011011011011101011010000011100100100110000011111000010010101001001110101010000011010101110001100111010000101000010110100011111001100001110011011001011010000100110010001000101111101001011100110101111110110100001100100110100000100100001011100111011000101111010...

output:

99977542
98746996
98989557
99015753
98938270
98605428
99504163
99699325
101118187
100862580
99993292
99728608
101006398
100940632
100522798
99799311
99585772
100035886
99976445
99131130
99309148
99370536
100535551
99600860
99595679
99735286
99976663
100435885
100334687
100103891
100055339
100160376
...

result:

ok 200000 lines

Test #8:

score: -100
Wrong Answer
time: 296ms
memory: 27968kb

input:

200000 200000
1101110010111101001110011011011100110000111011010010001110010111010000111100010101100111111010010100111110001001011000010110000100111111011110101101011011011101000010000110010011001011101000000100010110001100001010110010011101010100000011101111001110001110110000101101111011111101000101...

output:

10008345471
9978724639
9985258030
9985907293
9991673860
10011084416
10009425011
9997441308
9996266981
9988543457
10007145550
10003805687
9994416764
9995955504
10004097166
10015563170
10022793858
10028553181
10011635882
10026210037
10013171967
10011313687
10027633147
9986661473
9996002182
10017854287...

result:

wrong answer 1st lines differ - expected: '25901941', found: '10008345471'
English 繁體中文 简体中文

服务器时间: 2024-12-02 07:35:46 | 开源项目