QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#701310#8061. Add or MultiplyandaheAC ✓652ms225848kbC++172.7kb2024-11-02 14:01:572024-11-02 14:01:58

Judging History

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

  • [2024-11-02 14:01:58]
  • 评测
  • 测评结果:AC
  • 用时:652ms
  • 内存:225848kb
  • [2024-11-02 14:01:57]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define tl t[tp][p].l
#define tr t[tp][p].r
#define tlp t[tp][p].lp
#define trp t[tp][p].rp
#define LP t[tp][tlp]
#define RP t[tp][trp]
using namespace std;
const int N(200005);
const ll mod(1e9+7);
int tot[2];
ll a[N*2];
struct NODE
{
	int lp, rp, l, r;
	bool all = 0, tgl=0, tgr=0;
	ll ans=0, lans=0, rans=0, add=0;
}t[2][N*10];
bool Link(int mid, int tp) { return (a[mid*2]==tp); }
void update(int p, int tp)
{
	int l = tl, r = tr;
	int mid = l+r >> 1;
	t[tp][p].ans = ((LP.ans+RP.ans)%mod+Link(mid, tp)*(-LP.rans*LP.tgr-RP.lans*RP.tgl+LP.rans*RP.lans%mod)+mod)%mod;
	t[tp][p].ans = (t[tp][p].ans%mod+mod)%mod;
	
	t[tp][p].add = LP.add+RP.add;
	if(Link(mid, tp)) t[tp][p].add -= (LP.tgr^1)*a[mid*2-1]+(RP.tgl^1)*a[mid*2+1];

	if(LP.all && Link(mid, tp)) t[tp][p].lans = (LP.lans*RP.lans)%mod, t[tp][p].tgl = 1;
	else t[tp][p].lans = LP.lans, t[tp][p].tgl = LP.tgl;
	if(RP.all && Link(mid, tp)) t[tp][p].rans = (RP.rans*LP.rans)%mod, t[tp][p].tgr = 1;
	else t[tp][p].rans = RP.rans, t[tp][p].tgr = RP.tgr;

	t[tp][p].all = ((LP.all+RP.all == 2)&&Link(mid, tp));
}
void build(int l, int r, int tp)
{
	int p = ++tot[tp];
	if(l != r)
	{
		tl = l, tr = r;
		int mid = l+r>>1;
		tlp = tot[tp]+1;
		build(l, mid, tp);
		trp = tot[tp]+1;
		build(mid+1, r, tp);
		update(p, tp);
	}
	else 
	{
		t[tp][p].l = l, t[tp][p].r = r;
		t[tp][p].add = t[tp][p].lans = t[tp][p].rans = a[l*2-1];
		t[tp][p].all = 1;
	}
}
void modify(int p, int l, int r, int pos, int tp)
{
	if(l == r) { t[tp][p].add = t[tp][p].lans = t[tp][p].rans = a[l*2-1]; return; }
	int mid = (tl+tr)/2;
	if(pos <= mid) modify(tlp, l, mid, pos, tp);
	else modify(trp, mid+1, r, pos, tp);
	update(p, tp);
}
int main()
{
	//freopen("1.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m; cin >> n >> m;
	string inpu; cin >> inpu;
	for(int i = 0; i < n*2-1; ++i)
	{
		if(inpu[i] == '+') a[i+1] = 0;
		else if(inpu[i] == '*') a[i+1] = 1;
		else a[i+1] = inpu[i]-'0';
	}
	build(1, n, 0);
	build(1, n, 1);
	bool type = 1;
	cout<<(t[type][1].ans+t[type][1].add)%mod<<endl;
	for(int i = 1; i <= m; ++i)
	{
		char op; cin >> op;
		int x, y;
		if(op == 's')
		{
			cin >> x >> y;
			swap(a[x*2-1], a[y*2-1]);
			modify(1, 1, n, x, type);
			modify(1, 1, n, y, type);
			modify(1, 1, n, x, type^1);
			modify(1, 1, n, y, type^1);
		}
		if(op == 'f')
		{
			cin >> x;
			a[x*2] ^= 1;
			modify(1, 1, n, x, type);
			modify(1, 1, n, x+1, type);
			modify(1, 1, n, x, type^1);
			modify(1, 1, n, x+1, type^1);
		}
		if(op == 'a') type ^= 1;
		cout<<(t[type][1].ans+t[type][1].add)%mod<<endl;
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 15ms
memory: 224488kb

input:

3 4
2+3*4
s 1 2
a
f 2
a

output:

14
11
10
24
9

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 15ms
memory: 224412kb

input:

15 11
8*5*5*5*8*5*5*5*8*5*5*5+1+2+3
f 14
s 15 15
s 1 1
s 15 1
s 1 15
f 13
f 1
a
f 1
f 12
a

output:

1000000006
0
0
0
375000017
0
1000000006
125000014
101
74
75
999999965

result:

ok 12 lines

Test #3:

score: 0
Accepted
time: 255ms
memory: 225836kb

input:

200000 200000
3*5*6*3*7*3*4*7*2*9*2*7*5*9*2*9*5*4*6*3*7*2*8*6*6*8*4*2*4*5*5*8*9*4*9*2*7*5*4*3*9*4*8*5*5*6*5*3*8*5*9*2*7*8*8*6*7*6*6*5*7*8*3*7*3*5*9*3*7*5*6*8*2*5*6*5*2*9*7*8*7*4*9*3*9*5*4*5*4*3*4*4*9*6*4*5*4*8*9*8*5*9*9*9*8*6*9*6*5*8*5*5*6*9*2*6*9*6*5*4*7*6*5*4*8*3*5*8*5*5*5*7*4*2*4*8*2*5*6*3*9*7*5*...

output:

454019263
484673093
1099983
1099976
454019263
779145621
1099999
1099976
454019263
922488446
1099979
1099976
454019263
125627827
1100003
1099976
454019263
457373538
1100005
1099976
454019263
49928396
1100017
1099976
454019263
361222530
1099999
1099976
454019263
267241834
1099993
1099976
454019263
911...

result:

ok 200001 lines

Test #4:

score: 0
Accepted
time: 440ms
memory: 225692kb

input:

200000 200000
7*5*4+7+2*5*3*3+2*7*3+2+6+8+9*7+3*3+7+3*4*6*4+8+9*5*9*3+3+1+4+6+6+1*2+3*6+9*8*1*6*7*9+2*2+6+3+3*9*3+8*2+7+8+4*3+6+3+9*7*7+2*4*4*9*6*3*1+7+9*2*2+1+8*7+5+8+5+4+1*2+4*8+6+5*7+5+1+3+5+7+3+9+6+1+8+4+9+5+2+4*7*1*3*6*3+8+1*6*9*1+8+6+5+1*8*2*1*5*9+8+7+4+3+9+8*4*9*3*8*1*2*2*2+4+5+6*8*9+8*9+1*9*...

output:

408005284
408005259
631073017
631073018
408005259
408005259
408003705
408003734
408003695
407908446
407907522
407907744
407907928
407907041
407906852
631911412
631911441
631911418
408254984
408254607
408254489
408254471
408254478
408254478
408254498
408254498
408253239
623746881
623746889
623752256
...

result:

ok 200001 lines

Test #5:

score: 0
Accepted
time: 645ms
memory: 225580kb

input:

200000 200000
8*8*2*4*5*9*5+9*4*7+4*5*6+9*6*5*1+3*8*6*7+3*8*6*1*6*8*8*9*3+8*3*2*1*1*3*9*8*6+9*6*1*7*8*1*5*9*5+7+8*6*7*3*1*8+8*7*6+9*4*1*3*4*8*5*9*2*9*8*4*3*7*9*3*4*1*6+3+2*4*4*2*6*7*9+5*6*9*5*9*6*9*9+9*9*9*2*1*1*9+5+2*5*7*4*5+9*2*4*7+1+9*2+3*7*6*5*9*5*2*5*2+8*2*6*1*2*3*5*7*1*9*3*4*7*5+7*6*2*4*2*6*9*...

output:

767301573
389960204
683434916
683434916
500500896
547156224
244607693
323766435
588076952
588076952
587633157
562243370
884001688
282976856
282823928
145189538
80258726
80258726
87610286
935896501
607139343
920541057
920541057
920541016
473178251
611884042
731075273
728880281
211965293
211965293
839...

result:

ok 200001 lines

Test #6:

score: 0
Accepted
time: 563ms
memory: 225644kb

input:

200000 200000
6*2*6*6*8*2*7*5*5*4+2*1*1*4*2*9*4*3*2*9+2*2*9*4*6+3*2+3*3*6*4*8*9*6*1*6*2*7*1*2*2*7*1*4*4*4*9*3*8*1*1+4*6*1*2*1*6*6*5*2+4*3*2*9*8*1*3+7*4*5+3*6*9*1*1*8*2*5*9*8*7*4*6*4*7+2*3*6*2*9*2*1*9*5*9*6*3*2*7*4*1*5+5*3+1+4*1*1*4*3+4*6*3*8*9+6*9*5*3*8*8*6+3*8*6*1+7*9+6*5*4+8*7+1*9*1*2+7*7+8*1*7*3*...

output:

858987786
116350724
352539659
332243411
758331932
628758430
75168752
691368652
330613513
552745460
455834323
455832794
426112962
690445544
57334149
519544691
877935409
814873318
760543288
35219541
298403058
628850157
624150637
801910984
799094152
831393962
811849856
531021248
661988282
646311873
920...

result:

ok 200001 lines

Test #7:

score: 0
Accepted
time: 76ms
memory: 225620kb

input:

200000 200000
1*3*7*2+3*2*8*2*7+2*9*5+1*8*6*2*2+6*6*6*1*7*7*3+1+9*6*4*8+6*2*8*9*9*5*6*1*6*5*2*7*2*1*6*5*9+8*2*1*2*9+4*7*9*7*4*7*2+8*2*3*2*6*3*4*4*3*6*3*1*2*7*2*9*9*9*1*1*1*4*7*6*3*7+6+7*1+2*7*3*6*1*8*1*3*6*2*5*4*8*2*8*8*8*5*5*2*5+6*5*3*1*7+4*4*4*9*5*5*7*3*8*8*5*3*7*4*6+1*3*9*3*1+8*1*8*2*3*8*6*7*1*6*...

output:

116665646
1589703
116665646
1589703
116665646
1589703
116665646
1589703
116665646
1589703
116665646
1589703
116665646
1589703
116665646
1589703
116665646
1589703
116665646
1589703
116665646
116665645
1592016
116665645
1592016
116665645
1592016
116665645
1592016
116665645
1592016
116665645
1592016
11...

result:

ok 200001 lines

Test #8:

score: 0
Accepted
time: 611ms
memory: 225572kb

input:

200000 200000
1+1+2+1+2+3+3+7+3+3+1+5+1+7+1+3+9+9+7+1+8+4+6+8+9+2+7+4+2+5+3+4+2+5+6+5+5+7+8+9+9+5+3+7+6+3+8+9+4+5+9+4+8+7+7+9+3+5+4+7+9+5+3+2+1+4+9+2+7+4+2+6+5+3+5+4+2+9+6+6+5+4+6+1+1+4+2+1+2+9+7+6+4+2+4+3+8+8+1+4+4+2+5+3+3+5+5+3+7+6+3+6+8+7+3+8+2+1+5+6+8+2+8+3+6+8+4+3+1+4+7+6+3+2+8+5+3+4+3+1+4+5+8+...

output:

1000188
1000188
1000188
1000187
1000186
1000241
1000255
1000255
1000260
1000287
1000286
1000286
1000285
1000308
1000339
1000339
1000358
1000358
1000375
1000438
1000438
1000486
1000486
1000486
1000499
1000499
1000506
1000506
1000508
1000521
1000521
1000552
1000552
1000557
1000557
1000557
1000557
1000...

result:

ok 200001 lines

Test #9:

score: 0
Accepted
time: 652ms
memory: 225848kb

input:

200000 200000
4+9+8+2+8+2+2+7+6+6+8+7+5+6+9+2+6+3+6+5+7+5+6+6+8+2+7+9+2+1+2+7+5+2+5+6+4+2+9+3+7+7+4+3+7+2+1+3+3+3+9+2+7+1+3+6+8+9+3+1+2+8+2+1+8+5+7+2+3+9+4+1+2+9+6+8+5+9+3+2+5+3+6+4+5+3+8+8+8+2+4+6+1+1+8+1+3+9+8+1+2+6+2+8+7+3+7+4+8+4+6+7+4+4+2+2+1+2+3+4+9+9+3+2+8+5+7+5+2+4+1+1+3+4+1+1+9+4+4+9+8+1+4+...

output:

997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655
997655...

result:

ok 200001 lines

Test #10:

score: 0
Accepted
time: 549ms
memory: 225636kb

input:

200000 200000
6+7+4+8+8+8+5+2+8+4+9+2+8+7+6+5+9+9+1+3+2+5+3+3+8+2+1+2+5+5+5+4+8+2+2+5+9+3+8+5+8+6+9+7+1+5+2+5+2+5+4+2+1+7+4+2+9+5+8+7+4+1+7+4+2+9+3+9+9+4+9+9+3+5+7+1+9+8+5+6+9+8+9+2+3+7+6+9+1+1+3+7+1+2+8+1+3+8+2+5+2+8+2+7+4+6+6+9+3+4+3+9+7+8+1+4+4+7+1+2+8+6+3+1+5+1+8+4+1+4+1+3+2+7+8+5+7+7+6+3+6+3+2+...

output:

998896
998895
998894
998949
998956
998990
998993
998997
998998
999001
999008
999047
999051
999052
999081
999080
999079
999078
999083
999082
999097
999160
999201
999207
999242
999256
999287
999298
999305
999304
999305
999319
999326
999333
999332
999331
999344
999355
999369
999400
999407
999412
999412...

result:

ok 200001 lines

Test #11:

score: 0
Accepted
time: 412ms
memory: 225672kb

input:

200000 200000
8*7*7*9*8*7*7*9*9*7*7*7*9*9*7*7*7*9*8*9*9*9*9*8*8*9*8*9*9*8*9*9*9*7*8*9*9*9*7*9*9*9*7*9*9*9*9*8*7*7*8*8*8*8*7*9*8*9*7*7*7*8*9*7*8*8*9*9*9*9*7*8*7*8*7*7*9*8*8*7*9*7*8*7*7*7*9*7*7*8*7*9*9*7*8*7*8*7*7*7*7*8*8*7*9*8*9*8*9*8*8*9*8*7*8*8*8*8*7*7*7*9*8*9*9*7*7*9*9*7*7*9*7*8*8*7*9*8*9*8*9*8*7*...

output:

351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
351492537
...

result:

ok 200001 lines

Test #12:

score: 0
Accepted
time: 497ms
memory: 225640kb

input:

200000 200000
8*7*7*9*8*7*7*9*9*7*7*7*9*9*7*7*7*9*8*9*9*9*9*8*8*9*8*9*9*8*9*9*9*7*8*9*9*9*7*9*9*9*7*9*9*9*9*8*7*7*8*8*8*8*7*9*8*9*7*7*7*8*9*7*8*8*9*9*9*9*7*8*7*8*7*7*9*8*8*7*9*7*8*7*7*7*9*7*7*8*7*9*9*7*8*7*8*7*7*7*7*8*8*7*9*8*9*8*9*8*8*9*8*7*8*8*8*8*7*7*7*9*8*9*9*7*7*9*9*7*7*9*7*8*8*7*9*8*9*8*9*8*7*...

output:

230672968
230672968
263624687
263624687
263624687
296576568
296576568
230672968
230672968
296576568
296576568
230672968
230672968
296576568
259505712
259505712
259505712
296576568
296576568
296576568
296576568
230672968
259505712
230672968
230672968
259505712
259505712
230672968
230672968
296576568
...

result:

ok 200001 lines

Test #13:

score: 0
Accepted
time: 12ms
memory: 223508kb

input:

1000 1000
1+7+1+9+1+6*4+7*7+6*2*2*3*1+7*5+1*6*8+9*6+9+9*8*7+1*3*2*5+6*2*7*6+2*6+6*7*1*8*4*3+9+8+3+1+6*7*1+2*2+1*7+7+6+8+9+6+3*7+3+4*1*7*3*5*7+9*9+3*7+3+1+8+1+6*9*6*9*4*6+9+6+1*2*9+1+4+6+9*9+8+7*5*8+4*3*1*8+2*6*6*7+4*6*4*3+1*7*3*7+5+5*6+7+7+8*6+8+8*6+8*5+1+1+8*8*8*3+6*4*1+5*1+7+2*5+7+1*8*4+9+9*5+8+9+...

output:

4285380
676590
676589
676590
676649
4284680
4284661
4284770
4285466
4285147
678044
678221
678222
678311
4284948
4299504
4302512
4283648
4283699
612794
612794
4239843
612794
613554
627948
627995
627962
1008984
4237680
4237714
1008985
1008986
1008860
1008812
4233765
1008812
1009584
1016451
4233766
423...

result:

ok 1001 lines

Test #14:

score: 0
Accepted
time: 3ms
memory: 223556kb

input:

1000 1000
5*3*1+6+3+5*1*7+4+6+7+6*7+8*9*2+9+2*8+9+4*8*1*8*6*8*3+1*1+9+8*8+8*1+7*4+6*6+3*9*6+1*5+2+9*4+4*2+3*2*2+3+7+8*1*2+2+7+6+9+4*1+9*9*4+9*3*6*2+2*6+8+9*1*8+3*6+8+5*5*8+5+8+4+7+7*7*7*9+4*2*2*4+8+5*4+3+9+3+7*1+1+9*2+3+9+9+3+2+7*8+6*8+3*5*2+8+3*2+7*6+2*2*5+2*5*1*7+5*3+9*2+8+9*1*7*3*4*3+4*3*1*5+8+5+...

output:

1699575
1699815
1052535
1052536
1052881
1052833
1052839
1052834
1052762
1052817
1688308
1052817
1052817
1053251
1688396
1688388
1688416
1693019
1052986
1693019
1052986
1052986
1693019
1052986
1052988
1053132
1055475
1055914
984343
984296
984292
957751
1056813
1057187
1052784
1052789
1053101
1053096
...

result:

ok 1001 lines

Test #15:

score: 0
Accepted
time: 7ms
memory: 224280kb

input:

2 6
1*1
f 1
s 1 1
s 1 2
s 2 1
s 2 2
a

output:

1
2
2
2
2
2
1

result:

ok 7 lines

Test #16:

score: 0
Accepted
time: 12ms
memory: 224188kb

input:

2 1
9*8
s 1 2

output:

72
72

result:

ok 2 lines