QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#307714 | #8014. 新本格魔法少女 | for_to | 60 | 978ms | 41400kb | C++14 | 2.1kb | 2024-01-19 06:44:38 | 2024-01-19 06:44:39 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;
int n,m,q;
struct node{
int opt,l,r,v;
}s[N];
int f[N];
struct segment{
#define lson k<<1ll
#define rson lson|1ll
int w[N*4],tag[N*4];
void push_up(int k){
w[k]=w[lson]+w[rson];
}
void f(int k,int len,int v){
w[k]=(len*v);
tag[k]=v;
}
void push_down(int k,int l,int r){
if(tag[k]==-1) return;
int mid=(l+r)>>1ll;
f(lson,mid-l+1,tag[k]);
f(rson,r-mid,tag[k]);
tag[k]=-1;
}
void build(int k,int l,int r){
tag[k]=-1;
w[k]=0;
if(l==r) return;
int mid=(l+r)>>1ll;
build(lson,l,mid);
build(rson,mid+1,r);
}
void update(int k,int l,int r,int nl,int nr,int v){
if(l>=nl && r<=nr){
f(k,r-l+1,v);
return;
}
push_down(k,l,r);
int mid=(l+r)>>1ll;
if(mid>=nl) update(lson,l,mid,nl,nr,v);
if(mid<nr) update(rson,mid+1,r,nl,nr,v);
push_up(k);
}
int query(int k,int l,int r,int nl,int nr){
if(l>=nl && r<=nr) return w[k];
push_down(k,l,r);
int mid=(l+r)>>1ll,res=0;
if(mid>=nl) res+=query(lson,l,mid,nl,nr);
if(mid<nr) res+=query(rson,mid+1,r,nl,nr);
return res;
}
}t;
signed main(){
cin.tie(0); ios::sync_with_stdio(false);
cin>>n>>m>>q;
bool fl=0;
for(int i=1;i<=m;i++){
cin>>s[i].opt;
if(s[i].opt==1) cin>>s[i].l>>s[i].r>>s[i].v,fl=1;
else cin>>s[i].l>>s[i].r;
}
if(n<=5000){
int l,r;
while(q--){
cin>>l>>r;
t.build(1,1,n);
int res=0;
for(int i=l;i<=r;i++){
if(s[i].opt==1) t.update(1,1,n,s[i].l,s[i].r,s[i].v);
else res+=t.query(1,1,n,s[i].l,s[i].r);
}
cout<<res<<endl;
}
return 0;
}
if(!fl){
while(q--) cout<<0<<endl;
return 0;
}
int res=0;
t.build(1,1,n);
for(int i=1;i<=m;i++){
if(s[i].opt==1) t.update(1,1,n,s[i].l,s[i].r,s[i].v);
else res+=t.query(1,1,n,s[i].l,s[i].r);
f[i]=res;
}
int l,r;
while(q--){
cin>>l>>r;
cout<<f[r]<<endl;
}
return 0;
}
//10 5 4
//1 9 10 7
//1 7 10 9
//2 3 10
//1 10 10 1
//2 5 10
//2 5
//1 1
//3 4
//1 3
详细
Test #1:
score: 5
Accepted
time: 2ms
memory: 7736kb
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: 1ms
memory: 5676kb
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: 5
Accepted
time: 893ms
memory: 5920kb
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 724730383 10261117 1239181989 2287175021 1372474449 1250348 371071843 153933829 520831805 1543506490 808001543 59479545 2696569 890882157 1963386416 12546381 22417560 464332609 5635795 180739401 86357764 77199604 737960913 39774953 7590133 1769388054 1098297916...
result:
ok 5000 numbers
Test #4:
score: 5
Accepted
time: 754ms
memory: 5948kb
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: 834ms
memory: 5944kb
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: 5
Accepted
time: 978ms
memory: 5904kb
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 938807942 2134978510 54235687 168306782 18267562 344703118 739174828 591025501 26125268 108119368 1290819177 506928908 1426644181 789298612 10847284 748464260 203208925 81559279 101710978 2227236827 6753446 18824 740001853 1027314200 91892209 361330271 1473295893 118945920 69916...
result:
ok 4996 numbers
Test #7:
score: 5
Accepted
time: 211ms
memory: 19252kb
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: 168ms
memory: 19388kb
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: 5
Accepted
time: 397ms
memory: 41124kb
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:
2468271622976502 4698221336203047 2464245485338876 645680549315240 4137175050453070 3950418188801308 3431179684492738 4522966461353266 3166686806745582 5749341684382686 5655992044074729 5040293282968353 5319677263051754 788536277093141 5728837186825024 5510473350313701 3529728904982101 4619416125356...
result:
ok 499996 numbers
Test #10:
score: 5
Accepted
time: 349ms
memory: 40288kb
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:
6052992577626026 3382664487353801 1884084119561139 4903775722926407 3210035234431531 3584335605288938 884213945547262 3295062490109691 4664629263400943 2239831274910685 4245332811417453 3615086157849446 3713704632609047 2853449777151749 3326297007912742 1693113899010582 5193547170079661 610678361763...
result:
ok 499996 numbers
Test #11:
score: 5
Accepted
time: 363ms
memory: 39560kb
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:
990441926198121 1131783204405760 1841594455443916 1429945764520838 1342322224927645 1189072840223364 1018063528311989 559620378260513 989097224237378 1518129837354668 1867723561760663 1760356304733675 1042878888480154 1649535653395098 1368639223606920 267228899642801 1263976363580744 747690120151501...
result:
ok 500000 numbers
Test #12:
score: 5
Accepted
time: 383ms
memory: 41196kb
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:
9516852927305017 7740338485216257 1198276228367318 10740427176028746 7674707228336123 6385948644427168 8993322822222657 11525476199693268 8372851884764686 10841604116388888 4624556391191823 9183227648165112 12553205632815966 9069610675997904 11813755319797578 12039992183277874 9698983844179363 10370...
result:
ok 499997 numbers
Test #13:
score: 0
Wrong Answer
time: 176ms
memory: 20120kb
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:
74600085995823 147567615383136 154024060469100 305851463151114 67605298219022 141840622741953 294629792721820 248569243128021 248606152728039 231817208289154 57443677900942 270099210522695 147123191553518 243684711974609 50562738700449 172408838576192 67844488439068 167844882685179 263585140347984 1...
result:
wrong answer 1st numbers differ - expected: '11850130543160', found: '74600085995823'
Test #14:
score: 0
Wrong Answer
time: 148ms
memory: 21320kb
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:
275373132583440 623609165334304 489149823692502 274441509632900 282740177416286 421529735650002 372491318431367 196464536092640 652997349294837 586711256416423 314550773610233 605361560572441 259604181226141 213455243066966 317318021315761 632057269117277 640006666988826 410691929249873 499594980645...
result:
wrong answer 1st numbers differ - expected: '79495501365687', found: '275373132583440'
Test #15:
score: 0
Wrong Answer
time: 152ms
memory: 19680kb
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:
39796293955042 31985493950182 246298319939977 82285609554675 129658160125357 212879480845577 47328874682447 74810640209999 150624938634117 207514217201840 339902621340935 185969771522170 105395366321846 60360954073028 16949599033082 335933392249233 246344078967613 252222913926652 272803010565576 501...
result:
wrong answer 1st numbers differ - expected: '30619262894537', found: '39796293955042'
Test #16:
score: 0
Wrong Answer
time: 124ms
memory: 20204kb
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:
137571126207079 182762683622389 122417208342283 43184482209335 185924056459731 167248042655009 149947020475393 173748577306948 155677255520760 142220239408076 113492655142536 181741632757907 178589743889135 110839034084605 115170614481244 166714627266366 36515222744423 95180541576031 174716761175683...
result:
wrong answer 1st numbers differ - expected: '33260996367776', found: '137571126207079'
Test #17:
score: 0
Wrong Answer
time: 355ms
memory: 39968kb
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:
2380185702443964 2783352583812215 3089790112415079 1413866045193762 2360911278236236 3691167411552463 3763571886367247 1099439162229164 2278479567703728 16033105876906 2101144005899161 771548196558000 3129470705896414 1160053869962303 1375525825337392 840803895827302 879722427783704 3720173706288768...
result:
wrong answer 1st numbers differ - expected: '1942220657726821', found: '2380185702443964'
Test #18:
score: 0
Wrong Answer
time: 436ms
memory: 41196kb
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:
4524658555143624 4760942730002498 3450325229103030 3485608086049920 3693014354406156 1796188776690093 2486141874656180 4633975877064212 3295711910419215 3757446711233875 752147886869684 4099327308379576 1661107886121333 2855390143470583 4166963257635453 4859865035858362 3884928845684053 375799030545...
result:
wrong answer 1st numbers differ - expected: '1934994488313802', found: '4524658555143624'
Test #19:
score: 0
Wrong Answer
time: 379ms
memory: 41400kb
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:
3964159658258745 4173237855262578 1152553711811871 152873587085782 4253728246441389 4317937490094193 3611188376199648 2062408328484194 1586892107201883 992765963252416 1447077428060964 1011586600523726 4189538044605705 913633265027553 3683817414139593 3801883194690341 687358462985271 407558117078954...
result:
wrong answer 1st numbers differ - expected: '2430481205529290', found: '3964159658258745'
Test #20:
score: 0
Wrong Answer
time: 364ms
memory: 41188kb
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:
6498516711627878 9125998524154022 9647885822559764 11444085698016787 7599047129334941 9725917946820783 8930506404562329 5113394288302619 2186530380475158 7730824083184477 9936809546343460 11320458939891653 2330074793565933 8829701674155589 10023017173266094 10673170684615531 11771375332972256 696957...
result:
wrong answer 1st numbers differ - expected: '168449195555655', found: '6498516711627878'