QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#569402 | #9323. Segments and Subsets | Crysfly | AC ✓ | 33ms | 10180kb | C++14 | 3.2kb | 2024-09-16 22:37:41 | 2024-09-16 22:37:41 |
Judging History
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