QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#569402#9323. Segments and SubsetsCrysflyAC ✓33ms10180kbC++143.2kb2024-09-16 22:37:412024-09-16 22:37:41

Judging History

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

  • [2024-09-16 22:37:41]
  • 评测
  • 测评结果:AC
  • 用时:33ms
  • 内存:10180kb
  • [2024-09-16 22:37:41]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define mod 998244353
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 2000005
#define inf 0x3f3f3f3f

int n,x;
struct seg{
	int l,r;
}a[maxn];

int t[maxn],m;
int cnt[maxn];

struct bit{
	vector<int>tr;
	int n;
	void init(int N){n=N,tr=vector<int>(N+1,0);}
	void add(int x,int y){for(;x<=n;x+=x&-x)tr[x]+=y;}
	int ask(int x){
		int s=0;
		for(;x;x^=x&-x)s+=tr[x];
		return s;
	}
	void down(){For(i,1,n)tr[i]+=tr[i^(i&-i)];}
}tr;

void work()
{
	n=read(),x=read();m=0;
	For(i,1,n)a[i].l=read(),a[i].r=read(),t[++m]=a[i].l;
	sort(a+1,a+n+1,[&](auto x,auto y){
		if(x.r!=y.r)return x.r<y.r;
		return x.l>y.l;
	});
	sort(t+1,t+m+1),m=unique(t+1,t+m+1)-t-1;
	tr.init(m);
	For(i,1,n){
		int pos=lower_bound(t+1,t+m+1,a[i].l)-t;
		pos=m-pos+1;
		cnt[i]=tr.ask(pos),tr.add(pos,1);
	//	cout<<"cnt "<<i<<" "<<cnt[i]<<"\n";
	}
	modint res=0;
	For(i,1,n){
		res+=((a[i].r-a[i].l)%mod)*qpow(2,n-cnt[i]-1);
	}
	res=(qpow(2,n)-1)*(x%mod)-res;
	cout<<res.x<<"\n";
}

signed main()
{
	int T=read();
	while(T--)work();
	return 0;
}
/*

*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7816kb

input:

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

output:

10
28
806

result:

ok 3 number(s): "10 28 806"

Test #2:

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

input:

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

output:

7
34
32
26

result:

ok 4 number(s): "7 34 32 26"

Test #3:

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

input:

5
4 11
7 9
10 11
2 5
3 5
4 14
8 9
4 7
2 3
1 3
2 11
2 3
4 8
5 12
11 12
1 2
3 9
4 5
7 8
5 14
4 5
1 3
2 3
6 7
9 11

output:

113
162
23
284
338

result:

ok 5 number(s): "113 162 23 284 338"

Test #4:

score: 0
Accepted
time: 6ms
memory: 7684kb

input:

14240
10 139
40 42
49 50
36 43
58 59
41 42
56 57
29 59
4 26
11 12
37 38
7 142
31 32
18 20
28 36
13 15
8 24
19 20
14 15
4 178
17 24
27 37
23 24
4 14
9 151
32 77
26 27
7 31
16 19
18 19
25 27
30 31
39 46
9 10
4 166
53 55
46 62
8 38
61 62
5 116
13 69
77 99
107 108
113 115
1 7
4 107
6 10
9 10
8 9
16 23
4...

output:

132413
17394
2474
67849
2194
2204
1525
2402
4840
10271
1573
3162
73275
96408
1852
87358
11243
27254
3404
8073
3155
5618
1374
2553
1419
16269
10340
1704
47558
104268
8527
160178
10883
165528
14477
10212
92580
12254
2147
24902
1917
8572
2817
26840
4893
1477
23164
76337
1471
32403
30009
3868
72072
6113...

result:

ok 14240 numbers

Test #5:

score: 0
Accepted
time: 19ms
memory: 7824kb

input:

1183
67 184432519
157798264 162098307
61463016 61929620
19261812 22051269
43009439 43680646
39539805 40643488
63175579 63355228
56445172 60399059
40929072 41271211
28410073 28430429
29094038 38729629
90397858 90857715
42257412 49647849
3667918 3927138
64534492 75985283
68382164 69139864
30155585 342...

output:

296601823
803680947
313002846
103205003
832998296
888526697
968444095
894623231
162808943
514673067
96863741
579983906
504453257
933126155
694189812
752242226
885704017
219951716
125512388
677029609
71766576
621560538
850710227
113793601
938060087
227854018
580353674
964917386
38793984
76800413
7638...

result:

ok 1183 numbers

Test #6:

score: 0
Accepted
time: 23ms
memory: 8024kb

input:

6
10092 1000000000
363508199 363508200
83526710 83526711
62228397 62228398
10785122 10785123
142881720 142881721
326969975 326969976
196902996 196902997
364628773 367276438
30316363 30316837
184230432 184309499
56290098 56290099
18796466 18807903
53043889 53043890
39157593 39181129
136167459 1361735...

output:

663677307
831402723
332932072
241561407
480673812
810114628

result:

ok 6 numbers

Test #7:

score: 0
Accepted
time: 30ms
memory: 8080kb

input:

1
100000 982215789
16706586 16707917
21703577 21703921
121786356 121787001
16506040 16506453
501071 501072
115591022 115591024
16955452 16955453
118014679 118014680
115689327 115689328
2077247 2079498
16125451 16125452
20346638 20346639
2845494 2845495
120738689 120738902
118936842 118936843
2143058...

output:

915067396

result:

ok 1 number(s): "915067396"

Test #8:

score: 0
Accepted
time: 18ms
memory: 7716kb

input:

183
668 5175096
18700 18701
57510 57540
34387 34388
20911 20919
26261 26262
8560 8567
9143 9144
54205 54206
37768 38074
52126 52127
43125 43194
44948 44988
47767 47768
32764 32765
55843 55852
2075 2185
8336 8506
4098 4099
27839 27846
41402 41403
59577 59840
51035 51042
15968 15969
22265 22321
40626 ...

output:

114338028
887791533
654470550
559088769
166028317
47770351
355489118
353946086
878348994
797323053
138906712
785244866
187350454
995395070
565308852
245479059
859349352
274407036
916281179
911657390
589512225
377113808
779047812
786583770
454442966
855751195
920102732
952262497
661768099
721197115
8...

result:

ok 183 numbers

Test #9:

score: 0
Accepted
time: 32ms
memory: 10180kb

input:

2
75869 35421258
14950092 14950093
17312644 17313060
11621480 11621481
10473404 10473405
4455300 4455752
4671780 4671792
5910783 5910784
15825003 15825004
13314851 13315590
12190510 12190511
5623595 5623596
16243616 16243617
14449776 14449783
7766092 7766093
13529203 13529377
12475906 12475907
15209...

output:

821272052
69958347

result:

ok 2 number(s): "821272052 69958347"

Test #10:

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

input:

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

output:

31
46
13

result:

ok 3 number(s): "31 46 13"

Test #11:

score: 0
Accepted
time: 28ms
memory: 7868kb

input:

13
6981 20018956
671763 672264
1132244 1132246
723597 723598
369420 369421
1045721 1045722
792822 792823
816726 816766
1130044 1130164
559410 573479
776598 776785
1741162 1741424
1856193 1856313
281594 282062
461857 461858
186561 187505
420964 421017
968759 968777
866192 872444
1506286 1506287
17435...

output:

359927113
898307746
873299338
104522877
497497523
420651315
219523288
545330569
801121959
893705688
586980935
117674660
207774236

result:

ok 13 numbers

Test #12:

score: 0
Accepted
time: 33ms
memory: 9808kb

input:

2
90743 170368620
162444017 162444018
153891387 153891388
169201218 169201219
165106178 165106396
8708250 8712516
52828793 52829429
2579851 2579852
76541696 76541697
135470916 135470917
81016689 81020944
65512839 65512840
128512869 128512870
155534647 155534648
150988995 150988996
106565253 10656525...

output:

93307611
6703239

result:

ok 2 number(s): "93307611 6703239"

Test #13:

score: 0
Accepted
time: 24ms
memory: 7884kb

input:

13
7091 11452350
34454 34455
210171 210172
144799 144800
100414 100427
139634 139711
87568 87569
214014 214090
77957 77985
50277 50278
8962 8963
74235 74236
100941 100942
216095 216097
159801 159816
96968 96969
167526 167527
104772 104773
188660 188661
16214 16215
63618 63664
166808 166809
94797 948...

output:

138915696
114929473
646745898
492160847
103632699
997415986
897132746
465557300
256664947
978883425
623436196
82054504
611818847

result:

ok 13 numbers

Test #14:

score: 0
Accepted
time: 27ms
memory: 7796kb

input:

15
9950 11276542
51797 51943
289278 289279
661775 661779
663765 663766
75362 75363
584128 584129
481701 481702
27467 27473
489487 489488
42064 42067
646281 646289
614026 614084
381011 381012
490456 490459
620643 620698
663697 663698
605088 605093
70085 70086
500860 500861
10183 10204
8232 8289
67378...

output:

965487734
984125596
559975738
186603804
700269595
867332576
543385046
469092606
439049293
754648879
97822620
530992228
85472468
685646884
148772806

result:

ok 15 numbers

Test #15:

score: 0
Accepted
time: 27ms
memory: 7928kb

input:

14
7927 13137676
43335 43336
247084 247085
170125 170126
120412 120413
90563 90565
121247 121248
250192 250193
92264 92287
219649 219692
95433 95438
57088 57106
118177 118199
48275 48276
21484 21693
78788 78789
160694 160695
242657 242658
126444 126445
208042 208043
101303 101310
57289 57290
17406 1...

output:

633075155
771479025
156812653
668606052
26830603
25877727
259262220
994395717
493296058
922136637
188384457
654409437
944840209
603026394

result:

ok 14 numbers

Test #16:

score: 0
Accepted
time: 28ms
memory: 7900kb

input:

14
5188 668176
568002 568575
193217 193218
83195 83196
157478 157580
317328 317333
362855 363262
464557 464798
195336 197005
94714 94719
121891 122056
203574 203575
411803 411972
666449 666549
115704 115723
124445 124446
655959 655960
127632 127633
259761 259805
603744 603812
3235 3236
3903 3904
191...

output:

197120145
444839138
825007262
457047082
282033691
943900972
764622956
520856236
396211059
729311842
734955340
986626040
158900159
738128886

result:

ok 14 numbers

Test #17:

score: 0
Accepted
time: 28ms
memory: 7876kb

input:

13
7640 12337771
10576841 10576845
6161357 6162543
6780892 6782267
9776590 9776881
12137182 12137437
608994 609168
10746239 10746240
227966 229386
9528963 9529016
12247615 12247616
10722045 10722059
7854330 7855391
4261818 4261859
9583955 9583982
10747671 10748253
10235180 10239034
10522967 10522968...

output:

817138455
234435332
985039484
671994327
808427373
692311165
478612537
682415635
914713425
559346736
617752920
223776748
58551500

result:

ok 13 numbers

Test #18:

score: 0
Accepted
time: 23ms
memory: 7884kb

input:

15
5179 2472612
3991 3992
97557 97558
61828 61829
116890 116891
61772 61773
27962 27963
104942 104971
18465 18541
132811 132812
65026 65027
6368 6369
153347 153499
28 436743
146661 146662
171110 171131
47965 47966
102687 102688
54816 54890
120844 120860
63339 63359
31906 31907
66666 66667
41133 4114...

output:

105424124
504346584
536960182
227580473
932157776
398777582
173794763
255253833
765325341
24496052
734955406
758883541
684364280
158776819
378263493

result:

ok 15 numbers

Test #19:

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

input:

14
7728 13783740
487670 487671
522333 522334
481651 481652
482959 482960
395591 395592
24648 24665
18108 18117
15795 16016
402549 402550
553036 553119
618744 618745
399128 399165
564709 564710
564201 785948
637254 637321
577444 577445
440930 440931
24398 24401
422080 422081
534422 534423
643829 6438...

output:

51914009
159649847
203030583
875666536
9898263
444863074
688149631
52406209
672320606
67078102
684884636
689637516
489100205
517910317

result:

ok 14 numbers

Test #20:

score: 0
Accepted
time: 29ms
memory: 7988kb

input:

8
10811 808230811
1382404 1382405
1409425 1409426
1568458 1568460
1424542 1424555
1772750 1772751
1711140 1711141
1688638 1688639
1447034 1447155
1696308 1696320
1443774 1443780
1552272 1552303
1376703 1376704
1698746 1698747
1811843 1812024
1483314 1483315
1581616 1581631
1496816 1497254
1440975 14...

output:

185130323
793519805
194883203
270724469
185840728
839673790
676354908
117336993

result:

ok 8 numbers

Test #21:

score: 0
Accepted
time: 29ms
memory: 8132kb

input:

2
95178 1000000000
1581578 1581579
5213926 5213927
1793118 1793119
12470902 12471036
39032617 39032618
36415046 36415136
16033299 16037708
9872727 9872728
39479042 39479043
15953727 15953728
36048615 36048707
18843031 18843032
20471595 20471596
18908105 18908152
12907518 12907519
265183 265187
21385...

output:

621023198
988677488

result:

ok 2 number(s): "621023198 988677488"

Test #22:

score: 0
Accepted
time: 28ms
memory: 8072kb

input:

2
67775 1000000000
656646466 656646467
779348029 779348030
996118855 996133815
93131888 93138224
656727615 656727688
978971285 978971462
573352483 573363250
935556120 935560993
996370030 996370044
128672092 128844679
194402561 194403050
936262988 936283365
987235910 987235923
656679605 656679779
191...

output:

555206187
489027117

result:

ok 2 number(s): "555206187 489027117"

Test #23:

score: 0
Accepted
time: 31ms
memory: 10000kb

input:

2
52161 1000000000
100400 100401
1545675 1545678
1213808 1213829
1360210 1360428
1616535 1616536
862448 862558
1037574 1037575
1037483 1037505
182231 182275
825388 825399
581536 581537
534664 534666
267534 267535
183138 183139
724649 724650
293942 293995
1423714 1423721
788030 788031
286857 286863
7...

output:

974471666
983178260

result:

ok 2 number(s): "974471666 983178260"

Test #24:

score: 0
Accepted
time: 32ms
memory: 10004kb

input:

2
71728 1000000000
4927568 998362528
1733437 999425888
264266 999911243
1966850 999345124
907927 908026
2088994 999305117
4223225 998594996
3461265 3461335
2439459 2439495
5313266 998234887
5423237 998197422
2671771 2671792
4061248 998647213
5208625 5208666
2614078 2614145
3498865 998837862
2103615 ...

output:

798865569
210547288

result:

ok 2 number(s): "798865569 210547288"

Test #25:

score: 0
Accepted
time: 16ms
memory: 7740kb

input:

1835
14 1000000000
6485 7148
8033 999996716
1690 999999367
6409 999997397
10009 999995881
7655 999997128
785 1549
3272 999998700
8601 9445
7705 7973
2069 2858
5313 5859
3825 4351
4813 999998232
82 1000000000
34738 35670
45180 46149
62829 999980354
24868 999991331
60448 999981131
10931 11577
18769 99...

output:

713053256
645449675
146691499
728375688
916656007
383036972
415328892
41118737
4416096
911505216
339319561
943184818
318626627
124569622
173930766
74205697
132109261
850348725
651697716
171957962
500465203
908455522
151351108
254120512
624747269
793513677
452536566
626491431
883501852
131837160
2115...

result:

ok 1835 numbers