QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#339155 | #8014. 新本格魔法少女 | C1942huangjiaxu | 10 | 1600ms | 97196kb | C++14 | 3.1kb | 2024-02-26 20:17:48 | 2024-02-26 20:17:49 |
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];
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;
}
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));return 0;
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: 0
Wrong Answer
time: 11ms
memory: 49616kb
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:
result:
wrong answer Answer contains longer sequence [length = 100], but output contains 0 elements
Test #2:
score: 0
Wrong Answer
time: 5ms
memory: 50896kb
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:
result:
wrong answer Answer contains longer sequence [length = 100], but output contains 0 elements
Test #3:
score: 0
Wrong Answer
time: 7ms
memory: 48428kb
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:
result:
wrong answer Answer contains longer sequence [length = 5000], but output contains 0 elements
Test #4:
score: 0
Wrong Answer
time: 8ms
memory: 51216kb
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:
result:
wrong answer Answer contains longer sequence [length = 5000], but output contains 0 elements
Test #5:
score: 0
Wrong Answer
time: 8ms
memory: 50316kb
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:
result:
wrong answer Answer contains longer sequence [length = 4997], but output contains 0 elements
Test #6:
score: 0
Wrong Answer
time: 3ms
memory: 50160kb
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:
result:
wrong answer Answer contains longer sequence [length = 4996], but output contains 0 elements
Test #7:
score: 5
Accepted
time: 16ms
memory: 53320kb
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: 25ms
memory: 52340kb
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: 1385ms
memory: 89380kb
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:
wrong answer Answer contains longer sequence [length = 499996], but output contains 0 elements
Test #10:
score: 0
Wrong Answer
time: 1198ms
memory: 81164kb
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:
wrong answer Answer contains longer sequence [length = 499996], but output contains 0 elements
Test #11:
score: 0
Wrong Answer
time: 1600ms
memory: 97196kb
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:
wrong answer Answer contains longer sequence [length = 500000], but output contains 0 elements
Test #12:
score: 0
Wrong Answer
time: 1215ms
memory: 83112kb
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:
wrong answer Answer contains longer sequence [length = 499997], but output contains 0 elements
Test #13:
score: 0
Wrong Answer
time: 210ms
memory: 64964kb
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:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #14:
score: 0
Wrong Answer
time: 308ms
memory: 67748kb
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:
result:
wrong answer Answer contains longer sequence [length = 199998], but output contains 0 elements
Test #15:
score: 0
Wrong Answer
time: 313ms
memory: 69832kb
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:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #16:
score: 0
Wrong Answer
time: 405ms
memory: 73964kb
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:
result:
wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements
Test #17:
score: 0
Wrong Answer
time: 1412ms
memory: 88840kb
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:
wrong answer Answer contains longer sequence [length = 500000], but output contains 0 elements
Test #18:
score: 0
Wrong Answer
time: 1473ms
memory: 89640kb
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:
wrong answer Answer contains longer sequence [length = 499999], but output contains 0 elements
Test #19:
score: 0
Wrong Answer
time: 1306ms
memory: 81472kb
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:
wrong answer Answer contains longer sequence [length = 500000], but output contains 0 elements
Test #20:
score: 0
Wrong Answer
time: 1315ms
memory: 85396kb
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:
result:
wrong answer Answer contains longer sequence [length = 499996], but output contains 0 elements