QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310616 | #8014. 新本格魔法少女 | C1942huangjiaxu | 0 | 3761ms | 241564kb | C++14 | 4.9kb | 2024-01-21 16:13:49 | 2024-01-21 16:13:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1.5e6+5,B=1000,T=N/B+5;
typedef long long ll;
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);
}
struct node{
int l,r,v,t;
bool operator <(const node a)const{
return l<a.l;
}
};
struct mdf{
int l,r,v,tl,tr;
bool operator <(const mdf a)const{return tl<a.tl;}
}a[N];
set<node>S;
vector<node>e[N];
vector<pair<int,int> >g[T],h[N],bf[N];
vector<int>dl[N];
int n,m,q,ca,pos[N],L[T],R[T],pl[N],pr[N],p[2*B+5],cp,ip[N],d[2*B+5];
ll ans[N],v3[N],ad[2*B+5],sd[2*B+5],v1[N],vb[N],v2[N];
namespace block{
int _B,pos[N];
ll s1[N],s2[N],c1[1005],c2[1005];
void init(){
_B=sqrt(n);
for(int i=1;i<=n;++i)pos[i]=(i-1)/_B+1;
}
void clear(){
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
}
void upd(int x,int v){
if(x>n)return;
int lx=pos[x];
for(int i=x,j=min(lx*_B,n);i<=j;++i)s1[i]+=v,s2[i]+=1ll*x*v;
for(int i=lx+1,j=pos[n];i<=j;++i)c1[i]+=v,c2[i]+=1ll*x*v;
}
ll sum(int x){
if(!x)return 0;
int lx=pos[x];
return 1ll*(x+1)*(s1[x]+c1[lx])-s2[x]-c2[lx];
}
void upd(int l,int r,int v){
upd(l,v),upd(r+1,-v);
}
ll sum(int l,int r){
return sum(r)-sum(l-1);
}
};
int main(){
read(n),read(m),read(q);
for(int i=1,op,l,r,v;i<=m;++i){
read(op),read(l),read(r);
if(op==1){
read(v);
auto it=S.lower_bound({l,r,v,i});
if(it!=S.begin()){
--it;
node u=*it;
if(u.r>=l){
a[++ca]={l,u.r,-u.v,u.t,i};
S.erase(u);
S.insert({u.l,l-1,u.v,u.t});
}
}
while(1){
it=S.lower_bound({l,r,v,i});
if(it==S.end()||it->l>r)break;
node u=*it;
if(u.r>r){
a[++ca]={u.l,r,-u.v,u.t,i};
S.erase(u);
S.insert({r+1,u.r,u.v,u.t});
break;
}
a[++ca]={u.l,u.r,-u.v,u.t,i};
S.erase(u);
break;
}
S.insert({l,r,v,i});
a[++ca]={l,r,v,i,i};
}else a[++ca]={-l,-r,0,i,i};
}
sort(a+1,a+ca+1);
for(int i=1;i<=ca;++i){
if(!pl[a[i].tl])pl[a[i].tl]=i;
pr[a[i].tr]=i;
}
for(int i=1;i<=ca;++i)a[i].tr=pl[a[i].tr];
m=ca;
for(int i=1;i<=m;++i)pos[i]=(i-1)/B+1;
for(int i=1;i<=pos[m];++i)L[i]=(i-1)*B+1,R[i]=min(i*B,m);
for(int i=1,l,r;i<=pos[m];++i){
for(int j=L[i];j<=R[i];++j)if(a[j].l>0){
for(int k=j+1;k<=R[i];++k)if(a[k].l<0&&a[j].tr<k){
l=max(-a[k].l,a[j].l),r=min(-a[k].r,a[j].r);
if(l<=r)v1[j]+=r-l+1;
}
v1[j]=v1[j]*a[j].v;
}
}
for(int i=1,l,r;i<=q;++i){
read(l),read(r);
l=pl[l],r=pr[r];
int lx=pos[l],rx=pos[r];
if(lx!=rx){
g[lx+1].push_back({r,i});
h[r].push_back({l,i});
for(int j=R[lx];j>=l;--j)if(a[j].l>0&&a[j].r<=r)ans[i]+=v1[j];
}else bf[r].push_back({l,i});
}
for(int i=1,l,r;i<=pos[m];++i){
for(int j=L[i];j<=R[i];++j){
if(a[j].l<0){
for(int k=L[i];k<j;++k)if(a[k].l>0&&a[k].tr<j){
l=max(a[k].l,-a[j].l),r=min(a[k].r,-a[j].r);
if(l<=r)vb[k]+=r-l+1;
}
}else {
for(int k=L[i];k<j;++k)if(a[k].l<0&&a[j].tr<k){
l=max(-a[k].l,a[j].l),r=min(-a[k].r,a[j].r);
if(l<=r)vb[j]+=r-l+1;
}
}
for(auto v:bf[j]){
for(int k=v.first;k<=j;++k)if(a[k].l>0&&a[k].tr<=j)ans[v.second]+=vb[k]*a[k].v;
}
}
}
block::init();
for(int i=pos[m];i;--i){
block::clear();
for(int j=L[i];j<=m;++j)e[j].clear();
for(int j=L[i];j<=R[i];++j)if(a[j].l>0)e[a[j].tr].push_back({a[j].l,a[j].r,a[j].v,a[j].tr});
ll sum=0;
for(int j=L[i];j<=m;++j){
for(auto v:e[j])block::upd(v.l,v.r,v.v);
if(a[j].l<0)sum+=block::sum(-a[j].l,-a[j].r);
v3[j]+=sum;
}
for(auto v:g[i])ans[v.second]+=v3[v.first];
}
for(int i=1;i<pos[m];++i){
cp=2,p[1]=1,p[2]=n+1;
for(int j=L[i];j<=m;++j)dl[j].clear();
for(int j=L[i];j<=R[i];++j)if(a[j].l>0){
p[++cp]=a[j].l;
p[++cp]=a[j].r+1;
dl[a[j].tr].push_back(j);
}
sort(p+1,p+cp+1);
cp=unique(p+1,p+cp+1)-p-1;
for(int j=1;j<cp;++j)d[j]=ad[j]=0;
for(int j=1,l,r;j<cp;++j){
l=p[j],r=p[j+1]-1;
for(int k=l;k<=r;++k)ip[k]=j;
}
for(int j=L[i],l,r,lx,rx;j<=m;++j){
if(a[j].l<0){
l=-a[j].l,r=-a[j].r;
lx=ip[l],rx=ip[r];
if(lx==rx){
ad[lx]+=r-l+1;
}else{
ad[lx]+=p[lx+1]-l;
ad[rx]+=r-p[rx]+1;
++d[lx+1],--d[rx];
}
}
for(auto v:h[j])if(pos[v.first]==i){
for(int k=1;k<cp;++k)sd[k]=d[k]+sd[k-1];
for(int k=1;k<cp;++k)sd[k]=sd[k-1]+ad[k]+sd[k]*(p[k+1]-p[k]);
for(int k=R[i];k>=v.first;--k)if(a[k].l>0&&a[k].tr<=j)ans[v.second]+=(sd[ip[a[k].r]]-sd[ip[a[k].l-1]]-v2[k])*a[k].v;
}
for(auto v:dl[j]){
for(int k=1;k<cp;++k)sd[k]=d[k]+sd[k-1];
for(int k=1;k<cp;++k)sd[k]=sd[k-1]+ad[k]+sd[k]*(p[k+1]-p[k]);
v2[v]=sd[ip[a[v].r]]-sd[ip[a[v].l-1]];
}
}
}
for(int i=1;i<=q;++i)printf("%lld\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 11ms
memory: 184484kb
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 20213 2809 7888 7425 12422 3358 0 1856 1340 78 172 7806 0 6163 2029 25147 1545 14775 3050 18163 24888 4280 6312 9063 12900 7227 18296 0 11520 20516 2310 2331 19734 923 125 10946 26008 788 28186 449 3028 0 26751 31960 32489 13810 14775 3364 613 5811 30850 13479 8086 15041 10743 1149 258 4690 181...
result:
wrong answer 2nd numbers differ - expected: '19253', found: '20213'
Test #2:
score: 0
Wrong Answer
time: 15ms
memory: 183028kb
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 5727 4867 0 0 5727 0 0 2770 9673 0 5904 0 0 172 1220 0 3086 0 0 1798 3854 0 172 2113 0 6160 0 0 8163 0 1651 0 6208 0 407 1081 0 3854 0 0 2612 4653 404 2770 407 11290 3388 0 3883 0 4721 5727 1798 8163 4123 0 700 1798 0 713 5017 5242 5249 0 0 478 0 2612 3086 1340 4142 172 0 0 6768 3036 1948 0 61...
result:
wrong answer 3rd numbers differ - expected: '5513', found: '5727'
Test #3:
score: 0
Wrong Answer
time: 69ms
memory: 188552kb
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:
1425094152 147254782 48336009 6444034700 3513996992 90444651 6945184009 14192258038 7585881997 1250348 863756381 546659012 2459857421 8405804554 3316418152 88332164 2696569 4309083785 10839795311 12546381 218933407 1655873347 5635795 251555336 434238549 386087249 2214251656 40116035 7590133 89658052...
result:
wrong answer 1st numbers differ - expected: '234959455', found: '1425094152'
Test #4:
score: 0
Wrong Answer
time: 53ms
memory: 188756kb
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:
816860312 160478738 64574048 353956952 5895944 1054208 75492868 320968582 493100739 771713362 265549045 881298 563324033 233167978 95490487 7107372 1542460029 186934793 45589080 319879960 385798529 182611281 117455407 74160132 49300283 133162044 142092 609581868 533206 0 19085512 190211872 31782263 ...
result:
wrong answer 1st numbers differ - expected: '114655447', found: '816860312'
Test #5:
score: 0
Wrong Answer
time: 64ms
memory: 188692kb
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:
649821289 552250219 1729670316 3876271 62634178 1908582714 3022502373 174928743 97421423 253131479 67137212 72914470 290130288 1165828964 257301534 441327847 77215524 515524594 369070445 44969992 674887198 809487469 257850483 23251627 15722203 1349029118 51059967 386519751 1243210146 1277643043 9093...
result:
wrong answer 1st numbers differ - expected: '133792261', found: '649821289'
Test #6:
score: 0
Wrong Answer
time: 55ms
memory: 187200kb
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:
313099551 9018454537 4239501702 10078617522 383239576 515837342 18267562 580572413 1122702247 1982569764 78105904 224961355 4324177174 1296122540 6920288012 4770471984 10865974 3107988930 635174946 173769541 635908699 7778209203 6753446 18824 1656665545 2229774874 320988749 480509209 5296610678 2726...
result:
wrong answer 1st numbers differ - expected: '170506488', found: '313099551'
Test #7:
score: 0
Time Limit Exceeded
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:
result:
Test #8:
score: 0
Time Limit Exceeded
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:
result:
Test #9:
score: 0
Time Limit Exceeded
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:
result:
Test #10:
score: 0
Time Limit Exceeded
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:
result:
Test #11:
score: 0
Time Limit Exceeded
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:
result:
Test #12:
score: 0
Time Limit Exceeded
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:
result:
Test #13:
score: 0
Wrong Answer
time: 2119ms
memory: 221604kb
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:
1767186311064797 3139522826656680 1057172985491745 5509962339611907 210505967485666 9553180574865620 568146203287473 3319165949650923 171220007805887 8898883119999980 797784689863815 1960463649991705 11076037287725621 3559539210051554 2294703797670792 6602527294989527 1473038473088807 25553599000454...
result:
wrong answer 1st numbers differ - expected: '11850130543160', found: '1767186311064797'
Test #14:
score: 0
Wrong Answer
time: 3761ms
memory: 232680kb
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:
5743492738594232 8647889276547672 30318665955321487 25020712314337697 14375629436400685 22581638230485378 14454023021919394 13859341962286990 3023521270843054 7143431016414590 62577898259967 56973417978745606 2383957117804 24484358372905 2507286573209435 16681151645642578 45966916320508249 238503003...
result:
wrong answer 1st numbers differ - expected: '79495501365687', found: '5743492738594232'
Test #15:
score: 0
Wrong Answer
time: 3439ms
memory: 235584kb
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:
6274284266899383 3362632789932417 260041227240360 5618406152197011 24937781372638022 15044948890760071 4648586423776065 13337418642559184 14022038374776112 19619765465824493 57948618076779300 91042681118580 1883055857006855 6605845587726294 2785288807468658 71714364998427661 50243616637071445 601750...
result:
wrong answer 1st numbers differ - expected: '30619262894537', found: '6274284266899383'
Test #16:
score: 0
Wrong Answer
time: 3608ms
memory: 241564kb
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:
7245973089760122 8075439886208685 1437468891409090 795936729169354 2365862080417660 7865798690757840 364050563492170 11050404536752113 1377430863925390 4211630138311977 5423013489041031 3658448701298637 772105553042806 1143277278827275 6720790109569916 9334690240808910 810185438606191 76711606929862...
result:
wrong answer 1st numbers differ - expected: '33260996367776', found: '7245973089760122'
Test #17:
score: 0
Time Limit Exceeded
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:
result:
Test #18:
score: 0
Time Limit Exceeded
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:
result:
Test #19:
score: 0
Time Limit Exceeded
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:
result:
Test #20:
score: 0
Time Limit Exceeded
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 ...