QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#339166 | #8014. 新本格魔法少女 | C1942huangjiaxu | 30 | 3378ms | 104084kb | C++14 | 3.2kb | 2024-02-26 20:26:35 | 2024-02-26 20:26:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5,B=3000,T=N/B+5;
typedef unsigned long long ll;
typedef unsigned int uint;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
template<class rd>
void read(rd &x){
char c=getchar();
for(;c<48||c>57;c=getchar());
for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48);
}
uint n,m,q,l[N],r[N],v[N],a[N],p[N],id[N],tg[T],va[N],rv[N];
int d[N];
vector<tuple<uint,uint,ll> >e[N];
vector<pair<uint,ll> >g[N];
ll ans[N];
namespace b1{
ll s1[N],s2[1<<10];
uint lim;
void init(){lim=m>>10;}
inline void add(uint x,ll v){
s1[x]+=v,s2[x>>10]+=v;
}
inline ll sum(uint x){
ll res=0;
for(uint i=0,j=1024-(x&1023);i<j;++i)res+=s1[x+i];
for(uint i=(x>>10)+1;i<=lim;++i)res+=s2[i];
return res;
}
};
namespace b2{
ll s1[N],s2[1<<10];
inline void add(uint x,ll v){
for(uint i=0,j=x&1023;i<j;++i)s1[x-i]+=v;
for(uint i=0,j=x>>10;i<j;++i)s2[i]+=v;
}
inline void init(){
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
}
}
void work(uint ln,uint k,uint t){
for(uint i=1,x;i<=ln;++i)if(d[i]){
x=p[i];
b2::add(x,1ll*v[x]*d[i]);
g[t].emplace_back(x,-1ull*k*v[x]*d[i]);
d[i]=0;
}
}
void solve(uint L,uint R){
b2::init();
uint k=0,tg=0,ln=0;
for(uint i=1;i<=m;++i){
if(l[i]>R||r[i]<L)goto ct;
if(l[i]<=L&&R<=r[i]){
if(!v[i])++k;
else{
if(tg){tg=i;goto ct;}
for(int j=L;j<=R;++j)--d[a[j]];
work(ln,k,i);
ln=0,tg=i;
}
}else{
if(!v[i])goto ct;
uint _l=max(l[i],L),_r=min(r[i],R);
if(tg){
for(uint j=L;j<=R;++j)a[j]=1+(_l<=j&&j<=_r);
p[1]=tg,p[2]=i;
d[2]=_r-_l+1,d[1]=R-L+1-d[2];
tg=0,ln=2;
}else{
p[++ln]=i,d[ln]=_r-_l+1;
for(uint j=_l;j<=_r;++j)--d[a[j]],a[j]=ln;
uint ct=0;
for(uint j=1;j<=ln;++j)if(d[j])rv[j]=++ct,d[ct]=d[j];
ln=ct;
for(uint j=L;j<=R;++j)a[j]=rv[a[j]];
}
work(ln,k,i);
}
ct:;
for(auto &[x,y,z]:e[i])z+=(b2::s1[x]+b2::s2[x-1>>10])*k;
}
}
void bf(uint l,uint r,uint t){
if(l>r)return;
uint x=v[t],p=(l-1)/B;
if(!x){
if(tg[p])b1::add(tg[p],1ll*v[tg[p]]*(r-l+1));
else for(uint i=l;i<=r;++i)b1::add(a[i],va[i]);
}else{
if(tg[p]){
uint w=v[tg[p]];
for(uint i=p*B+1,j=p*B+B;i<=j;++i)a[i]=tg[p],va[i]=w;
tg[p]=0;
}
for(uint i=l;i<=r;++i)a[i]=t,va[i]=x;
}
}
int main(){
bool fg=true;
read(n),read(m),read(q);
b1::init();
for(uint i=1;i<=m;++i){
read(v[i]),read(l[i]),read(r[i]);
if(v[i]==1)read(v[i]),fg=false;
else v[i]=0;
}
if(fg){
while(q--)puts("0");
return 0;
}
for(uint i=1,l,r;i<=q;++i){
read(l),read(r);
e[r].emplace_back(l,i,0);
}
for(uint i=1;i<=n;i+=B)solve(i,min(i+B-1,n+1));
for(uint i=1;i<=m;++i){
uint lx=(l[i]+B-2)/B,rx=r[i]/B;
if(lx>rx)bf(l[i],r[i],i);
else{
bf(l[i],lx*B,i),bf(rx*B+1,r[i],i);
if(!v[i]){
for(uint j=lx,x;j<rx;++j)if(x=tg[j])b1::add(x,v[x]*B);
}else for(uint j=lx;j<rx;++j)tg[j]=i;
}
for(auto [x,y]:g[i])b1::add(x,y);
for(auto &[x,y,z]:e[i])z+=b1::sum(x);
}
for(uint i=1;i<=m;++i)for(auto [x,y,z]:e[i])ans[y]+=z;
for(uint i=1;i<=q;++i)printf("%lld\n",ans[i]);
return 0;
}
詳細信息
Test #1:
score: 5
Accepted
time: 3ms
memory: 52364kb
input:
100 100 100 2 80 86 2 15 49 1 11 100 25 2 22 36 2 37 100 1 14 16 49 2 74 90 2 28 76 1 43 45 78 1 54 56 27 1 73 75 29 2 34 81 2 51 90 1 13 14 52 1 72 73 2 2 18 58 2 44 58 1 83 85 30 1 86 88 69 1 29 31 25 1 92 94 19 1 48 49 16 1 55 57 91 1 98 100 42 2 13 96 2 50 83 1 23 25 39 1 84 85 55 1 43 45 5 1 90...
output:
8086 19253 2809 6928 7105 24622 3358 0 1856 1260 78 172 17231 0 6163 2029 24290 1545 14375 3050 17203 23928 3560 6312 8103 11940 6267 17698 0 10720 19937 2310 2331 18774 923 125 10066 24991 788 27169 449 3028 0 25814 30943 31472 12850 14375 3364 613 4931 48343 13159 8086 14081 9783 1149 258 4690 181...
result:
ok 100 numbers
Test #2:
score: 5
Accepted
time: 0ms
memory: 55848kb
input:
100 100 100 1 56 92 5 1 5 9 91 1 70 92 77 1 45 52 90 1 37 38 36 1 9 10 1 2 1 72 1 79 80 86 2 40 98 1 96 97 89 2 46 78 2 41 58 1 57 58 65 1 73 74 44 1 20 21 54 1 95 96 61 1 23 24 40 1 60 61 48 1 17 18 65 1 43 44 68 1 44 45 7 1 28 29 4 1 10 11 37 1 14 15 44 1 69 70 18 1 33 34 52 1 15 16 67 1 62 63 64 ...
output:
0 700 5513 4848 0 0 5513 0 0 2751 10719 0 5885 0 0 172 1201 0 3067 0 0 1779 3835 0 172 2094 0 5946 0 0 7884 0 1651 0 6189 0 407 1081 0 3835 0 0 2593 5577 404 2751 407 13799 3369 0 3864 0 4702 5513 1779 7884 3974 0 700 1779 0 713 5941 6166 5230 0 0 478 0 2593 3067 1321 4123 172 0 0 6749 3036 1929 0 6...
result:
ok 100 numbers
Test #3:
score: 0
Wrong Answer
time: 13ms
memory: 54776kb
input:
5000 5000 5000 1 4070 5000 3145 2 1139 3698 1 798 799 3999 1 2423 2424 2414 1 836 838 518 1 3605 3607 2831 1 525 526 2041 1 4734 4736 1862 2 2408 3821 1 1394 1395 1129 2 601 3026 2 728 4428 1 567 569 4843 2 4235 4835 1 3568 3569 1157 1 3043 3045 4342 1 1813 1815 1888 1 2992 2993 4810 1 1862 1864 112...
output:
234959455 32410138 47895605 1345462704 724715222 10261117 1238472957 2286086730 1371719212 1250348 371923780 153933829 520831805 1542732506 808001543 59694953 2696569 890847026 1962937624 12546381 22417560 464332609 5635795 181533576 86275209 76373657 737102928 39774953 7590133 1768419319 1098297916...
result:
wrong answer 5th numbers differ - expected: '724730383', found: '724715222'
Test #4:
score: 5
Accepted
time: 11ms
memory: 57812kb
input:
5000 5000 5000 1 3198 5000 2085 1 2688 2781 3934 1 663 664 1655 1 472 473 4369 1 822 823 75 2 798 2403 1 518 519 4434 1 4022 4023 3962 1 121 122 1996 1 568 569 2710 1 2908 2909 418 1 429 430 4757 1 1361 1362 4590 1 4439 4440 4849 1 3104 3105 2808 1 78 79 1549 1 2111 2112 2281 1 3405 3406 4240 1 2739...
output:
114655447 19433053 35915790 65614418 2476899 665630 20272239 61553396 72380629 114749301 65069600 881298 103684015 34129779 11855040 3208516 228433692 31692347 23672327 59493928 58289510 64897362 18474211 13657972 14996772 50859224 71046 84176051 533206 0 3412089 46601293 5753887 33429474 30861172 8...
result:
ok 5000 numbers
Test #5:
score: 5
Accepted
time: 11ms
memory: 57872kb
input:
4997 5000 4997 1 924 4997 4123 1 1508 1568 759 1 1148 1190 3389 1 908 952 122 1 4976 4997 4100 1 4578 4637 1736 1 2780 2821 3570 1 2830 2874 1796 1 351 391 1 1 762 801 3091 1 2060 2105 398 1 4572 4618 615 1 941 971 853 1 4395 4397 4934 1 4573 4574 4506 1 3697 3698 83 2 112 2024 1 310 311 1941 1 2116...
output:
133792261 139082018 293669691 3861707 34233830 279117403 1018970742 35243052 56047746 41576886 19209005 38995139 76194093 193774179 104584925 59187495 6752467 84435341 101847867 23142906 124266639 150193133 107905427 11004395 5034444 214897499 26673236 75854241 300218884 196777973 175768847 13761372...
result:
ok 4997 numbers
Test #6:
score: 0
Wrong Answer
time: 14ms
memory: 53260kb
input:
4997 4999 4996 2 4368 4799 2 2119 4764 2 4434 4464 1 2035 4706 4296 1 519 522 2387 2 3 2084 1 4748 4755 461 2 2812 4626 1 4801 4805 2427 1 611 615 2155 2 772 2397 2 1443 2197 2 392 792 1 3032 3036 2776 2 3148 4757 1 3661 3678 3968 1 3901 3921 2378 1 143 164 531 1 3337 3360 3189 2 679 2911 1 1436 145...
output:
170506488 2306515380 938330881 2134586394 54235687 168306782 18267562 344703118 739174828 591025501 26125268 108119368 1290819177 506928908 1426253961 788973863 10847284 748464260 203208925 81559279 101341440 2226992542 6753446 18824 739134556 1027314200 91830883 361330271 1473086630 118945920 69916...
result:
wrong answer 3rd numbers differ - expected: '938807942', found: '938330881'
Test #7:
score: 5
Accepted
time: 20ms
memory: 52216kb
input:
499998 499998 500000 2 45317 481911 2 205023 267850 2 229212 496395 2 311928 408362 2 60781 309919 2 5271 471569 2 428188 498422 2 92261 439291 2 169892 354633 2 154209 351949 2 39872 442239 2 17793 200874 2 111458 165313 2 35630 448969 2 144408 434923 2 150127 486605 2 87239 425125 2 221549 283735 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 500000 numbers
Test #8:
score: 5
Accepted
time: 14ms
memory: 51576kb
input:
499996 500000 499996 2 416226 432058 2 352324 435508 2 284349 418508 2 331919 481387 2 123642 260653 2 443789 449866 2 304455 480845 2 25402 269023 2 88509 334117 2 91159 399658 2 354630 412055 2 27378 126849 2 43994 304769 2 352338 413477 2 441505 499446 2 230203 287653 2 386 34219 2 77130 483544 2...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 499996 numbers
Test #9:
score: 0
Wrong Answer
time: 2799ms
memory: 95960kb
input:
499999 499997 499996 1 242721 499999 95404 2 46103 133768 2 374074 441419 1 24121 24525 460791 1 296358 334367 213389 1 333891 339996 192126 2 271641 289312 1 159292 235107 359363 2 281766 283959 2 68186 255669 2 112532 201134 2 281439 287449 2 265345 398433 1 495720 499897 85179 2 336233 383598 1 3...
output:
2557686692890554 5051528055117139 2553337060836380 650515201864554 4406565626846386 4194708737747262 3612787092572055 4848697543381331 3319645945302745 6291485760016268 6179578725859515 5450914250086439 5779490851939770 795830337036058 6266742663772931 6005990038979313 3722214010907229 4960092390000...
result:
wrong answer 1st numbers differ - expected: '2468271622976502', found: '2557686692890554'
Test #10:
score: 0
Wrong Answer
time: 3258ms
memory: 89404kb
input:
499996 499998 499996 2 127334 135648 2 250092 494065 2 202618 237080 1 365995 485247 159366 1 461761 461763 167619 1 161295 165395 156081 2 118953 278863 1 31995 32188 13920 2 211226 376698 2 125014 312511 1 248692 248694 369316 2 23909 438451 1 90793 222688 109394 1 405548 405549 283104 2 54420 263...
output:
6204747873266088 3413834937365471 1887402292622817 4992167589650281 3236373316233019 3621624339315424 882304368934540 3323733636241648 4742125362258217 2247296519301478 4305608289821372 3653293783747414 3755036650015947 2871410176487490 3355864355058802 1694946415820613 5296158183501697 626202848175...
result:
wrong answer 1st numbers differ - expected: '6052992577626026', found: '6204747873266088'
Test #11:
score: 0
Wrong Answer
time: 2387ms
memory: 104084kb
input:
499999 499996 500000 1 263967 499999 193060 1 473673 473677 256364 1 112817 112820 147747 2 47560 75007 1 19751 19754 272463 1 147343 147345 432368 1 385248 385251 111981 1 98114 98117 384182 1 186894 186898 304739 1 13283 13285 1641 1 127923 127925 168790 2 59949 123247 2 76677 91972 1 138037 13803...
output:
1098370375800456 1270877541351016 2204109301152369 1650421357669401 1536780256941726 1342078795932531 1131736062629822 597275627777215 1096733737080713 1765934351236058 2240448616232123 2091948293545838 1161953366027509 1941493765591219 1570542800554672 277830980235234 1436530907746845 8115156644624...
result:
wrong answer 1st numbers differ - expected: '990441926198121', found: '1098370375800456'
Test #12:
score: 0
Wrong Answer
time: 3378ms
memory: 93288kb
input:
499999 499995 499997 1 163879 499999 440480 2 420164 470414 1 443882 499999 62525 1 313171 499999 294789 1 469407 469540 44668 2 25119 191405 2 172689 455667 2 110136 338451 2 218391 398188 1 486533 486654 93435 2 95706 256203 2 196989 304612 2 326480 401308 2 54460 198784 1 271793 271898 320340 2 9...
output:
-1060051498740060 -629615602244481 848896490239322 -1357325468650737 -613768763486530 -306091344732654 -933836377724927 -1546519126638151 -782196186781461 -1382325033639869 111062815301820 -979833665536309 -1804157289101537 -952226863721226 -1619384925966450 -1675724143261326 -1105091217003765 -1268...
result:
wrong answer 1st numbers differ - expected: '9516852927305017', found: '-1060051498740060'
Test #13:
score: 0
Wrong Answer
time: 1105ms
memory: 71320kb
input:
200000 200000 200000 2 31803 80740 2 112818 127167 1 131322 154428 90611 2 11014 192282 2 41925 115417 2 5816 159028 2 111819 126655 2 37293 172866 2 27835 145099 2 124446 162824 2 104521 118016 2 40376 127391 1 195318 195319 149596 2 41040 179839 2 61847 94626 2 69878 181705 2 28968 179132 2 132543...
output:
2186578506661 6433114308985 2960717064243 25931153671444 293401201958 12131893763339 6234428919188 13964646969968 1693376430961 22009089128475 934424420319 11744684650043 13480601539958 14010023609428 1620030497017 13495838425223 1726713316068 6568437183546 4964808844514 10710688595145 8995635486116...
result:
wrong answer 1st numbers differ - expected: '11850130543160', found: '2186578506661'
Test #14:
score: 0
Wrong Answer
time: 952ms
memory: 76272kb
input:
199995 199998 199998 1 159195 199995 13044 2 86976 157151 1 64762 102114 152625 1 61813 63647 178420 1 82889 85481 125381 1 51586 54321 77506 2 45182 109756 1 181575 184132 133556 2 28331 132281 2 17325 40861 2 42257 191103 2 147228 198059 2 75171 155696 1 139100 140799 154126 1 188327 190311 76827 ...
output:
11460898441307 21534029631343 60154377894072 598268079970248 24608857902229 44698120914216 24824492157787 448195828064662 2299438732338 18222142862435 173894698889 98028121260334 13711085746 58852066325 6865795003750 40382020812950 92086070302679 43346008540015 18409847410518 27105212603776 86668230...
result:
wrong answer 1st numbers differ - expected: '79495501365687', found: '11460898441307'
Test #15:
score: 0
Wrong Answer
time: 793ms
memory: 79120kb
input:
199999 199996 200000 1 179926 199999 32711 1 1042 1044 112146 2 26640 43359 1 178347 178351 169789 2 32064 164957 2 81951 117742 1 179853 179856 73377 2 66862 193241 2 10596 28181 2 49117 162750 1 13331 13333 43998 2 26996 197910 1 161366 161369 84391 2 127515 184183 1 66412 66416 97202 2 49708 5634...
output:
14147132482558 8138876479646 3132677462610 22717946938942 80545679738480 87061413940302 13821608916637 36434169075074 66596257188703 104862288675590 287569047088224 767678814638 10587721438950 20873557936043 4207827429957 304436972514376 196810526931457 209907109177646 9692739544 841192006066 361473...
result:
wrong answer 1st numbers differ - expected: '30619262894537', found: '14147132482558'
Test #16:
score: 0
Wrong Answer
time: 579ms
memory: 80780kb
input:
200000 200000 200000 1 59821 200000 173244 1 190307 190309 110936 1 112341 112342 4761 1 124738 124740 84834 1 3047 3049 102534 2 114052 180833 2 72832 109679 2 84797 91295 1 191583 191584 141834 1 185318 185320 87703 1 117000 117002 109533 1 80539 80540 105603 1 24207 24209 111543 1 83298 83299 140...
output:
7146490464501 10391453635928 1957749242811 407999672838 4865043826465 9021344361019 757560982028 11868852938946 2536591848700 5108745917008 4730736089490 6840035524930 2063856254768 1364286784244 5448854276627 10142906244281 346729127157 848017704459 13494199569398 8944256490492 10748979266838 82425...
result:
wrong answer 1st numbers differ - expected: '33260996367776', found: '7146490464501'
Test #17:
score: 0
Wrong Answer
time: 2795ms
memory: 96628kb
input:
500000 500000 500000 2 430331 460074 1 364723 500000 100669 1 250319 250342 82754 1 438542 441692 403146 1 463281 463283 433598 2 257762 468063 2 48944 155558 2 353640 481169 1 84674 84675 290827 2 146697 229831 2 468564 488452 2 5108 66751 1 23182 45112 201883 2 282890 447793 1 32871 33375 376198 1...
output:
740315118265144 1410530750974 673376129929373 243840937903067 115045035559733 35404793118610 182318580564723 189250699458312 44587052536786 11209013261 594243815658338 14952586855477 688364775812396 95676640353676 204811090800107 204466896059 334211504 756928005674920 70583020472574 1252579529607368...
result:
wrong answer 1st numbers differ - expected: '1942220657726821', found: '740315118265144'
Test #18:
score: 0
Wrong Answer
time: 2788ms
memory: 98716kb
input:
500000 499995 499999 2 227886 411572 2 211683 333769 1 250096 500000 235662 1 426728 426927 304290 2 57626 245045 2 274989 390864 2 128937 178776 1 131741 131862 102941 1 98436 98438 22052 1 166478 166479 223278 1 450334 450336 468682 1 235946 235947 469845 1 472838 472839 386149 1 94197 94199 37254...
output:
884504316519049 453161076945913 168085435789904 114532263431169 68495544947737 128858163447784 234753144500532 448780620758076 726844235125 752223422191436 6634830133529 16427963084120 140030468413954 368635061396767 295254987424881 571072987371027 891886577562440 342030122823593 135525552659580 228...
result:
wrong answer 1st numbers differ - expected: '1934994488313802', found: '884504316519049'
Test #19:
score: 0
Wrong Answer
time: 3120ms
memory: 91704kb
input:
500000 500000 500000 1 483553 500000 33628 1 469113 469115 99122 2 331771 461807 2 132277 227909 1 409018 409020 67790 2 239961 327023 2 71363 250145 2 194504 394975 2 112739 357223 2 29586 226312 1 365927 365929 56596 2 37108 464107 2 260079 467849 1 132248 132250 77986 2 192853 237448 2 361959 386...
output:
1761120347466375 1670261976606594 334635844622607 13794609918419 1714541186826920 82884903271927 739309055526040 74397285460008 392005358255270 141649779798490 502604532896683 283811968407171 503035414260856 251861142263856 96639939943030 564126752087660 156119879868881 58829796073688 78371377560508...
result:
wrong answer 1st numbers differ - expected: '2430481205529290', found: '1761120347466375'
Test #20:
score: 0
Wrong Answer
time: 3283ms
memory: 95136kb
input:
499999 499999 499996 2 212908 238055 1 460268 499999 317714 2 420753 465452 1 184130 194219 347230 1 24358 31202 484414 2 261874 280744 1 382916 389593 121902 2 998 230297 1 83691 94553 138191 2 357537 469176 1 478043 489289 9664 2 49390 163924 1 496313 499999 485644 2 307553 482205 1 148359 158827 ...
output:
3603410784868 81450352919727 82463057524454 135169565896877 51155767787129 7630614089667 18706165012462 1262032809300 7979177445213 7808955042307 24837932795310 34805153206030 3594644588140 84773496871258 14920598609902 123707635567085 44708935674722 34607268396625 14585952039829 61576282786205 1824...
result:
wrong answer 1st numbers differ - expected: '168449195555655', found: '3603410784868'