QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#308776 | #8014. 新本格魔法少女 | crazy_sea | 20 | 5642ms | 58592kb | C++14 | 2.9kb | 2024-01-20 12:39:12 | 2024-01-20 12:39:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10,B=600,K=N/B+1;
int n,m,Q,mx;
vector<pair<int,int>> v[N];
namespace b1//O(1) Modify
{
ll t1[N],t2[N];
void add(int x,ll a)
{
t1[x]+=a,t2[(x-1)/B]+=a;
}
ll qry(int x)
{
int k1=(x-1)/B,k2=(x-1)%B;
ll s=0;
for(int i=0;i<B-k2;i++) s+=t1[x+i];
for(int i=k1+1;i<=mx;i++) s+=t2[i];
return s;
}
}
namespace b2//O(1) Query
{
ll t1[2][N],t2[2][K+10];
void add(int x,ll a,ll b)
{
int k1=x%B,k2=x/B;
for(int i=0;i<k1;i++) t1[0][x-i]+=a,t1[1][x-i]+=b;
for(int i=0;i<k2;i++) t2[0][i]+=a,t2[1][i]+=b;
}
void init()
{
for(int i=1;i<=m;i++) t1[0][i]=t1[1][i]=0;
for(int i=0;i<K;i++) t2[0][i]=t2[1][i]=0;
}
ll qry(int x,int k)
{
int w=(x-1)/B;
return t1[1][x]+t2[1][w]+(t1[0][x]+t2[0][w])*k;
}
}
int p[N],id[N],d[N],l[N],r[N],a[N],tag[K+10];
ll ans[N],op[N];
void work(int len,int k)
{
for(int i=1,x;i<=len;i++)
if(d[i])
{
x=p[i];
b2::add(x,1ll*op[x]*d[i],-1ll*k*op[x]*d[i]);
d[i]=0;
}
}
void solve(int L,int R)
{
int num=0,tag=0,len=0;
b2::init();
for(int i=L;i<=R;i++) a[i]=0;
for(int i=1;i<=m;i++)
{
if(l[i]>R||r[i]<L) continue;
if(l[i]<=L&&R<=r[i])
{
if(op[i]==-1) num++;
else
{
for(int i=L;i<=R;i++) d[a[i]]--;
work(len,num);
len=0,tag=i;
}
}
else
{
if(op[i]==-1) continue;
int x=max(l[i],L),y=min(r[i],R);
if(tag)
{
for(int j=L;j<=R;j++)
a[j]=1+(x<=j&&j<=y);
len=2;
p[1]=tag,p[2]=i;
d[2]=y-x+1;
d[1]=R-L+1-d[2];
}
else
{
p[++len]=i;
for(int j=x;j<=y;j++)
d[a[j]]--,d[a[j]=len]++;
}
work(len,num);
}
for(auto k:v[i]) ans[k.second]+=b2::qry(k.first,num);
}
}
void brute(int l,int r,int k)
{
if(l>r) return;
int x=op[k],w=(l-1)/B;
if(x==-1)
{
if(tag[k]) b1::add(tag[k],1ll*(r-l+1)*op[tag[k]]);
else for(int i=l;i<=r;i++) b1::add(a[i],op[a[i]]);
}
else
{
if(tag[w])
for(int i=(w-1)*B+1;i<=w*B;i++) a[i]=tag[w];
for(int i=l;i<=r;i++) a[i]=k;
tag[w]=0;
}
}
int main()
{
// freopen("mfsn.in","r",stdin);
// freopen("mfsn.out","w",stdout);
scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=m;i++)
{
scanf("%lld%d%d",&op[i],&l[i],&r[i]);
if(op[i]==2) op[i]=-1;
else scanf("%lld",&op[i]);
}
for(int i=1,l,r;i<=Q;i++)
{
scanf("%d%d",&l,&r);
v[r].push_back({l,i});
}
for(int i=1;i<=n;i++) a[i]=0;
for(int i=1;i<=m;i++)
{
int k1=(l[i]+B-2)/B,k2=r[i]/B;
if(k1>k2) brute(l[i],r[i],i);
else
{
brute(l[i],k1*B,i);
brute(k2*B+1,r[i],i);
if(op[i]==-1)
{
for(int j=k1,x;j<k2;j++)
if((x=tag[j])) b1::add(x,op[x]*B);
}
else for(int j=k1;j<k2;j++) tag[j]=i;
}
for(auto k:v[i]) ans[k.second]=b1::qry(k.first);
}
for(int i=1;i<=n;i+=B)
solve(i,min(i+B-1,n));
for(int i=1;i<=Q;i++) printf("%lld\n",ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 0ms
memory: 36724kb
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: 35732kb
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: 7ms
memory: 36396kb
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:
74447625 15185070 10569030 245150359 145426263 4653108 308901773 252769359 122424323 660444 105682530 70991136 146506753 320852722 121254413 10482913 592507 402442871 103142559 6700833 10410053 75424165 899354 28111990 65135693 29327285 85244639 14378561 2695624 222556815 165325249 113438273 1144163...
result:
wrong answer 1st numbers differ - expected: '234959455', found: '74447625'
Test #4:
score: 0
Wrong Answer
time: 11ms
memory: 36512kb
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:
24417413 5570989 8213755 4184790 1717380 236734 6148743 6380182 15140213 23114960 2897044 199918 1769865 4736839 3556566 673124 38195696 992637 9709287 9010211 17297250 14024903 4201394 662459 4004969 77401 17464 65799251 1235304 0 490673 8338777 712751 2968643 6321540 11570973 1235304 1657916 0 104...
result:
wrong answer 1st numbers differ - expected: '114655447', found: '24417413'
Test #5:
score: 0
Wrong Answer
time: 5ms
memory: 35160kb
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:
32675397 23750247 58941264 1040699 10322165 14126502 34797325012 14181011 17068401 14044074 6651430 9985577 23194463 47680738 22573623 19574720 2294935 6721332 27557985 8392102 36630799 34500528 17083841 4420419 837403 7520189 10437674 8028129 51668786 31188259 15298346 47406556 58786506 120324774 7...
result:
wrong answer 1st numbers differ - expected: '133792261', found: '32675397'
Test #6:
score: 0
Wrong Answer
time: 3ms
memory: 35352kb
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:
87973207 42049789 139208006 133637332 16979433 39512654 11431717 101891410 101344750 106380410 7397571 20465334 266024706 75420502 393462017 10345696 14765421 77254160 46796312 20421794 31364111 503347388 3791875 2064 291326116 180081450 82873269 243545306 224403095 106326888 15232684 9707478 266384...
result:
wrong answer 1st numbers differ - expected: '170506488', found: '87973207'
Test #7:
score: 5
Accepted
time: 5642ms
memory: 54516kb
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: 5629ms
memory: 52468kb
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: 3658ms
memory: 56484kb
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:
152377928479281 361125957292677 18706742755936 13292825998073 1077872542118001 376207132673791396 95960664358345306 21464427020532 241572756516067 167844916729350834 1651085382184400 230298861559713252 23198730221059 13719512208205 24274049011815 3113713236184244 293757573752958 19393682419595 26099...
result:
wrong answer 1st numbers differ - expected: '2468271622976502', found: '152377928479281'
Test #10:
score: 0
Wrong Answer
time: 4225ms
memory: 56560kb
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:
911669440146948 2640421790583102 174143550933937 698922808819414 24816004188023 21586952665705194 15442892352792673 22839805742912 114238333381013644 570185979478675 36894278946313971 25585618794401 158710512469739 46384810628472395 56171416606062 158792485190270 61717897484898029 334991330015097835...
result:
wrong answer 1st numbers differ - expected: '6052992577626026', found: '911669440146948'
Test #11:
score: 0
Wrong Answer
time: 3044ms
memory: 56480kb
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:
4152540451484 59383481725852 93226994557453 3641159270479 655493172636951 596181608644164 38291019057863 4804280232109 3900990429191 98414941655382 5622715128513 1143869363398050 1931276720339613 949971822451209 43647819016101 67781235937292 31999653633395 3173945576593 2808256403940 18654864181577 ...
result:
wrong answer 1st numbers differ - expected: '990441926198121', found: '4152540451484'
Test #12:
score: 0
Wrong Answer
time: 4452ms
memory: 56620kb
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:
428960705821332 277130258881151277 95855802443738 93749237133021319 473204339849736293 176631283674079770 64713731947491 1014646831362709530 61229390224379278 884866370771025477 59868113353054 550146327108217611 556078614122105880 302514083561315 8427736132127824 1795596707783724 2261963942046685 88...
result:
wrong answer 1st numbers differ - expected: '9516852927305017', found: '428960705821332'
Test #13:
score: 0
Wrong Answer
time: 848ms
memory: 48580kb
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:
2949793315 21561022039904 101246382686 27686533667981 317909027230 285588696032 8424341818810 155884234376 2804842958722 14507907251249 4814024244447 17105544345392 164156255563 30143421223122 43313301145 36760820042338 537254894045 430808324376 3361019814167 9136264819383 9132735532595 496768964742...
result:
wrong answer 1st numbers differ - expected: '11850130543160', found: '2949793315'
Test #14:
score: 0
Wrong Answer
time: 633ms
memory: 48568kb
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:
2295465850171 41957647836551 3515052761113 5504283873411810 261899173457473 1845269821830 5064354122554 4963642068567146 104938714566 184724577042626 857846541937 3668446967611 9681649459 28941282472 1609676840916 2281938466787 165747797621226 297522417632819 6370755819051 1790955617923 744474089724...
result:
wrong answer 1st numbers differ - expected: '79495501365687', found: '2295465850171'
Test #15:
score: 0
Wrong Answer
time: 667ms
memory: 50624kb
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:
114716909413 4725257707355 10465288632 125468894514 20796511533232 28257550252679 12997425911 66933605816 173444445639 180306213597 97598919989573 230969418081 38534329738 107662878507 13240926557126 110256140013337 3293199713 1156375559755 79573116 512331298826 29454965 394841616943 28041290096097 ...
result:
wrong answer 1st numbers differ - expected: '30619262894537', found: '114716909413'
Test #16:
score: 0
Wrong Answer
time: 551ms
memory: 48452kb
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:
31197590327009 154315977863 31827677864 21165973026 45346982353 147213004284 4452076036 24361932714087 49973361610 8576081459 16714795068 83546471725 46366097943 30630603065 77247219342 263763589709 4659155391 11171431524 390058575414 73780655636 179687924308 123709524715 3667601981 60837444308 3982...
result:
wrong answer 1st numbers differ - expected: '33260996367776', found: '31197590327009'
Test #17:
score: 0
Wrong Answer
time: 3902ms
memory: 56520kb
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:
3713323692325 929213496476 1917595913448 590917033846 85132243748164 35851979215981 129761275900572 311817317461198 76151269425 43502367144 1127354584916597 29220577982592 2086609400091 94281624652563 923927179915 29965121118 7559310 1774676741478 176681194519 1934373566175569 152543796240348 744914...
result:
wrong answer 1st numbers differ - expected: '1942220657726821', found: '3713323692325'
Test #18:
score: 0
Wrong Answer
time: 3763ms
memory: 56476kb
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:
5071325411453 305791616321311 777090129958 713343564548 75356114454 700796771066 743704292853 371436836024420 1657143553370 1678296228064 49363847418 19616827461 789757065608 1202937391817 1287657480923 378143776051 334179895387 462817786473 580785435135 427971368058362 294978626112 1477875695947 25...
result:
wrong answer 1st numbers differ - expected: '1934994488313802', found: '5071325411453'
Test #19:
score: 0
Wrong Answer
time: 4505ms
memory: 56568kb
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:
2174940109509891 4370330711392 590523410744935 5834064756993 1032861098540547 8557621736376 799386596623 80384067214722 402967724286688 150462659443 700087860097362 304989924532 10605909079825 215952814358 168771118184 1596744877025 170880023783789 19787344627 234793701112 177185790084 2413886805261...
result:
wrong answer 1st numbers differ - expected: '2430481205529290', found: '2174940109509891'
Test #20:
score: 0
Wrong Answer
time: 4774ms
memory: 58592kb
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:
242716362963 4795607873212 2171297257821612 1943656928885 1190371913805399 87973263237515 296299637662458 2636720946153 22813543466181 53929917451923 2485569510496 3641433486161 31232801796077 2187546208663 1252025521475 1876816873643892 289478330347 980503283571 1380413445043 59255883836509 1664160...
result:
wrong answer 1st numbers differ - expected: '168449195555655', found: '242716362963'