QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#706590	#6733. Moniphant Sleep	TheZone	AC ✓	618ms	50856kb	C++20	5.7kb	2024-11-03 12:27:45	2024-11-03 12:27:46

Judging History

你现在查看的是最新测评结果

[2024-11-03 12:27:46]
评测

测评结果：AC
用时：618ms
内存：50856kb

查看

[2024-11-03 12:27:45]
提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,q;
struct tag{
    int premin,presum,sufsum,opt,c,has4;
    tag(){premin=presum=sufsum=c=has4=0;opt=1;}
    tag(int _premin,int _presum,int _sufsum,int _opt,int _c,int _has4):
        premin(_premin),presum(_presum),sufsum(_sufsum),opt(_opt),c(_c),has4(_has4){

        }
};
inline void outag(tag a)
{printf("%d %d %d %d %d %d\n",a.premin,a.presum,a.sufsum,a.c,a.opt,a.has4);}
inline tag merge(tag A,tag B)
{
    tag ret;
    
    if(A.has4&&B.has4)
    {
        ret.premin=A.premin;
        ret.presum=A.presum;
        ret.opt=B.opt;
        ret.has4=1;
        if(A.opt==1||A.sufsum+B.premin<A.c)
        {
            ret.sufsum=A.sufsum+B.presum+B.sufsum;
            if(ret.opt==2)ret.c=B.c+A.sufsum+B.presum;
        }
        else
        {
            ret.sufsum=A.c+B.sufsum;
            if(ret.opt==2)ret.c=A.c+B.c;
        }
    }
    else if(!A.has4&&!B.has4)
    {
        ret.premin=min(A.premin,A.presum+B.premin);
        ret.presum=ret.sufsum=A.presum+B.presum;
        if(A.opt==1||A.sufsum+B.premin<A.c)
        {
            ret.opt=B.opt;
            if(ret.opt==2)ret.c=A.sufsum+B.c;
        }
        else
        {
            ret.opt=2;
            ret.c=A.c;
        }
    }
    else if(!A.has4)
    {
        ret.premin=min(A.premin,A.presum+B.premin);
        ret.sufsum=B.sufsum;
        ret.opt=B.opt;
        ret.c=B.c;
        ret.has4=1;
        if(A.opt==1||A.sufsum+B.premin<A.c)
            ret.presum=A.presum+B.presum;
        else 
            ret.presum=A.c;
    }
    else
    {
        ret.premin=A.premin;
        ret.presum=A.presum;
        ret.sufsum=A.sufsum+B.presum;
        ret.has4=1;
        if(A.opt==1||A.sufsum+B.premin<A.c)
        {
            ret.opt=B.opt;
            if(ret.opt==2)ret.c=B.c+A.sufsum;
        }
        else 
        {
            ret.opt=2;
            ret.c=A.c;
        }
    }
    return ret;
}
tag val[maxn<<2];
inline void pushtg(int i,tag v)
{
    val[i]=merge(val[i],v);
    return;
}
inline void pushdown(int i)
{
    pushtg(i<<1,val[i]);
    pushtg(i<<1|1,val[i]);
    val[i]=tag();
}
inline void update(int i,int l,int r,int L,int R,tag v)
{
    if(L<=l&&r<=R){pushtg(i,v);return;}
    int mid=l+r>>1;pushdown(i);
    if(L<=mid)update(i<<1,l,mid,L,R,v);
    if(R>mid)update(i<<1|1,mid+1,r,L,R,v);
}
inline int ask(int i,int l,int r,int p)
{
    //printf("!%d %d\n",l,r);
    //outag(val[i]);
    if(l==r)return val[i].has4?val[i].presum+val[i].sufsum:val[i].presum;
    int mid=l+r>>1;pushdown(i);
    if(p<=mid)return ask(i<<1,l,mid,p);
    else return ask(i<<1|1,mid+1,r,p);
}
inline void build(int i,int l,int r)
{
    val[i]=tag();
    if(l==r)return;
    int mid=l+r>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
}
const int ini=5e5;
int main()
{
    scanf("%d%d",&n,&q);
    build(1,1,n);
    while(q--)
    {
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==5)printf("%d\n",ask(1,1,n,l)+ini);
        else if(opt==1)update(1,1,n,l,r,(tag){0,1,1,1,0,0});
        else if(opt==2)update(1,1,n,l,r,(tag){-1,-1,-1,1,0,0});
        else if(opt==3)update(1,1,n,l,r,(tag){0,0,0,2,0,0});
        else if(opt==4)update(1,1,n,l,r,(tag){0,0,0,1,0,1});
        //for(int i=1;i<=n;i++)printf("?%d %d\n",i,ask(1,1,n,i));putchar('\n');
    }
}
/*#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,q;
struct tag{
    int premin,presum,sufsum,opt,c,has4;
    tag(){premin=presum=sufsum=c=has4=0;opt=1;}
    tag(int _premin,int _presum,int _sufsum,int _opt,int _c,int _has4):
        premin(_premin),presum(_presum),sufsum(_sufsum),opt(_opt),c(_c),has4(_has4){

        }
};
inline void outag(tag a)
{printf("%d %d %d %d %d %d\n",a.premin,a.presum,a.sufsum,a.c,a.opt,a.has4);}
inline tag merge(tag A,tag B)
{
    tag ret;
    
    if(A.has4&&B.has4)
    {
        ret.premin=A.premin;
        ret.presum=A.presum;
        ret.opt=B.opt;
        ret.has4=1;
        if(A.opt==1||A.sufsum+B.premin<A.c)
        {
            ret.sufsum=A.sufsum+B.presum+B.sufsum;
            if(ret.opt==2)ret.c=B.c+A.sufsum+B.presum;
        }
        else
        {
            ret.sufsum=A.c+B.sufsum;
            if(ret.opt==2)ret.c=A.c+B.c;
        }
    }
    else if(!A.has4&&!B.has4)
    {
        ret.premin=min(A.premin,A.presum+B.premin);
        ret.presum=ret.sufsum=A.presum+B.presum;
        if(A.opt==1||A.sufsum+B.premin<A.c)
        {
            ret.opt=B.opt;
            if(ret.opt==2)ret.c=A.sufsum+B.c;
        }
        else
        {
            ret.opt=2;
            ret.c=A.c;
        }
    }
    else if(!A.has4)
    {
        ret.premin=min(A.premin,A.presum+B.premin);
        ret.sufsum=B.sufsum;
        ret.opt=B.opt;
        ret.c=B.c;
        ret.has4=1;
        if(A.opt==1||A.sufsum+B.premin<A.c)
            ret.presum=A.presum+B.presum;
        else 
            ret.presum=A.c;
    }
    else
    {
        ret.premin=A.premin;
        ret.presum=A.presum;
        ret.sufsum=A.sufsum+B.presum;
        ret.has4=1;
        if(A.opt==1||A.sufsum+B.premin<A.c)
        {
            ret.opt=B.opt;
            if(ret.opt==2)ret.c=B.c+A.sufsum;
        }
        else 
        {
            ret.opt=2;
            ret.c=A.c;
        }
    }
    return ret;
}
tag val[maxn<<2];
inline void pushtg(int i,tag v)
{
    val[i]=merge(val[i],v);
    return;
}
inline void pushdown(int i)
{
    pushtg(i<<1,val[i]);
    pushtg(i<<1|1,val[i]);
    val[i]=tag();
}
inline void update(int i,int l,int r,int L,int R,tag v)
{
    if(L<=l&&r<=R){pushtg(i,v);return;}
    int mid=l+r>>1;pushdown(i);
    if(l==r)return;
    }
}*/

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 50788kb

input:

output:

result:

ok 1 number(s): "500004"

Test #2:

score: 0

Accepted

time: 0ms

memory: 50788kb

input:

output:

500001
499999

result:

ok 2 number(s): "500001 499999"

Test #3:

score: 0

Accepted

time: 604ms

memory: 50788kb

input:

500000 500000
2 132991 371170
5 15281 15281
1 278642 397098
2 152103 176573
2 13797 47775
3 139320 370045
3 79054 432340
3 82556 212775
4 270171 469418
5 148000 148000
3 371255 401414
5 71051 71051
2 358945 473071
2 231663 265401
2 20243 58131
1 247710 313373
5 154549 154549
1 17317 233265
5 37602 3...

output:

result:

ok 99850 numbers

Test #4:

score: 0

Accepted

time: 610ms

memory: 50788kb

input:

500000 500000
1 82261 414004
4 128531 435780
1 182288 357334
1 384377 425512
5 400207 400207
5 12158 12158
4 287819 439382
4 273623 387675
4 141825 285941
3 69773 134995
4 29380 264126
1 294648 422834
5 39538 39538
3 142540 417717
5 234932 234932
3 203802 448531
4 70427 154922
5 350852 350852
1 1512...

output:

result:

ok 99856 numbers

Test #5:

score: 0

Accepted

time: 608ms

memory: 50808kb

input:

500000 500000
5 72042 72042
3 413594 434238
2 361496 397187
1 269630 487427
3 242649 269514
1 54440 379912
4 186602 218641
3 276439 423353
3 135538 386886
1 18494 105835
2 280844 281961
4 295419 431095
2 371614 462384
3 287902 310870
4 16615 433795
4 190316 318613
3 212017 398069
5 9605 9605
4 91266...

output:

result:

ok 100105 numbers

Test #6:

score: 0

Accepted

time: 618ms

memory: 50672kb

input:

500000 500000
2 5190 91049
4 128857 445467
3 223530 277888
2 40982 105310
1 407309 471677
2 28575 133349
1 32121 490377
5 253892 253892
3 302998 419525
2 113017 482504
1 69934 143033
4 48272 361234
5 2861 2861
1 73851 222387
4 353590 463398
5 246538 246538
4 172175 241916
3 123903 463282
5 265403 26...

output:

result:

ok 100018 numbers

Test #7:

score: 0

Accepted

time: 609ms

memory: 50672kb

input:

500000 500000
1 92884 302553
3 55209 426930
4 274477 421174
1 116041 243779
2 184334 487953
3 377378 416732
2 78059 458714
1 117519 134853
5 30966 30966
4 6896 243400
4 133516 387611
5 274315 274315
4 1255 321875
1 223029 472140
1 134662 463400
1 271092 375546
4 154845 453545
2 283001 468220
3 20643...

output:

result:

ok 100214 numbers

Test #8:

score: 0

Accepted

time: 615ms

memory: 50812kb

input:

500000 500000
5 417190 417190
5 343155 343155
3 238196 397249
2 190674 437636
3 292166 453486
3 33110 230933
1 203367 265293
5 224931 224931
4 147852 361144
5 267505 267505
3 135127 384589
3 223472 441256
1 149972 160456
1 207060 334058
1 461029 486155
1 180058 382221
3 122724 138722
2 438731 448303...

output:

result:

ok 99758 numbers

Test #9:

score: 0

Accepted

time: 604ms

memory: 50804kb

input:

500000 500000
5 463523 463523
5 113643 113643
2 381674 410504
1 22966 114703
5 16811 16811
5 273752 273752
2 272169 420247
2 71593 112069
4 171364 379367
3 56291 187294
1 151339 169092
1 191063 393959
4 96567 345115
5 47859 47859
2 447869 485334
1 148875 281623
3 57575 88435
3 7881 207243
5 84967 84...

output:

result:

ok 99487 numbers

Test #10:

score: 0

Accepted

time: 596ms

memory: 50808kb

input:

500000 500000
4 315829 368195
3 414015 486000
2 148601 309648
3 323477 435058
2 7730 312072
1 91960 499853
5 243073 243073
4 308460 375604
1 40395 150056
5 116054 116054
3 142106 406335
3 166868 380856
4 101797 181638
1 31743 237233
4 190434 259395
1 91100 332530
3 156661 282976
5 98708 98708
1 1997...

output:

result:

ok 99671 numbers

Test #11:

score: 0

Accepted

time: 613ms

memory: 50728kb

input:

500000 500000
2 338729 402306
2 260139 296789
2 348628 378006
4 151959 263061
3 274633 499362
3 132916 136988
3 19132 495822
3 47431 471607
2 144550 199941
3 52929 115332
1 17302 132635
2 195980 480390
3 173564 289435
1 219579 286571
2 319857 387911
1 444872 466260
3 117298 214290
2 245260 322033
1 ...

output:

result:

ok 99951 numbers

Test #12:

score: 0

Accepted

time: 608ms

memory: 50856kb

input:

500000 500000
4 43080 426035
2 446418 498842
2 261117 446761
3 174657 283077
3 475449 484835
5 346061 346061
2 312006 425604
4 154903 350468
1 53920 374405
2 289214 481287
5 181600 181600
3 72854 222601
5 289827 289827
5 18524 18524
4 304780 417551
1 307684 430391
2 238310 271890
1 196257 364172
5 4...

output:

result:

ok 100352 numbers