QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#124284#6630. Triangle Collectionstarrylasky0 1ms9836kbC++142.0kb2023-07-14 16:33:092023-07-14 16:33:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-14 16:33:11]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:9836kb
  • [2023-07-14 16:33:09]
  • 提交

answer

///yl/hs/bx/yl
#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
// #define int long long
#define ld long double
#define pr pair<int,int>
#define mpr make_pair
using namespace std;

const int N = 4e5+5,mod = 1e9+7;
inline int read()
{
   int s=0,w=1; char ch=getchar();
   while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
   while(  ch>='0'&&ch<='9')  {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
   return s*w;
}
inline int Mod(int x) {return x>=mod?x-mod:x;}
inline void addmod(int &x,int y) {x=Mod(x+y);}

namespace starrylasky
{
    int n,Q,c[N];
    struct SGT
    {
        #define lson u<<1
        #define rson u<<1|1
        #define mid (l+r>>1)
        LL sl[N<<2],sr[N<<2],sd[N<<2];
        inline void pushup(int u)
        {
            int res=min(sl[lson],sr[rson]);
            sd[u]=sd[lson]+sd[rson]+res;
            sl[u]=sl[lson]+sl[rson]-res;
            sr[u]=sr[lson]+sr[rson]-res;
        }

        inline void work(int u)
        {
            int res=min(sl[u],sr[u]);
            sl[u]-=res; sr[u]-=res; sd[u]+=res;// cerr<<sl[u]<<" "<<sr[u]<<" "<<sd[u]<<"\n";
        }

        inline void update(int u,int l,int r,int pos)
        {
            if(l==r) return sl[u]=c[l]&1,sr[u]=(l&1?c[l+1>>1]>>1:0),sd[u]=0,work(u);
            if(mid>=pos) update(lson,l,mid,pos);
            else update(rson,mid+1,r,pos);
            pushup(u);
        }
    }sgt;

    inline void Main()
    {
        n=read(),Q=read();
        fep(i,1,n) c[i]=read();
        fep(i,1,2*n) sgt.update(1,1,2*n,i);
        fep(i,1,Q)
        {
            int p=read(),v=read(); c[p]+=v;
            sgt.update(1,1,n,p); sgt.update(1,1,n,2*p-1);
            printf("%lld\n",sgt.sd[1]+2*sgt.sr[1]/3);
        }
    }
}

signed main()
{
    int _T=1;
    while(_T--) starrylasky::Main();
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 1ms
memory: 5768kb

input:

1 23
1485
1 -12
1 -30
1 -20
1 6
1 24
1 5
1 31
1 14
1 -34
1 -22
1 -45
1 37
1 46
1 9
1 22
1 -9
1 9
1 -46
1 -47
1 39
1 36
1 -36
1 50

output:

491
481
474
476
484
486
496
501
489
482
467
479
495
498
505
502
505
490
474
487
499
487
504

result:

ok 23 numbers

Test #2:

score: -5
Wrong Answer
time: 0ms
memory: 9680kb

input:

12 1
13 79 59 21 32 13 85 40 74 15 49 56
3 31

output:

204

result:

wrong answer 1st numbers differ - expected: '189', found: '204'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 1ms
memory: 9796kb

input:

1999 2000
1 1 1 1 0 2 0 2 1 0 2 1 2 2 2 1 2 0 0 1 2 2 0 1 0 1 0 2 0 0 2 1 1 1 1 0 1 2 1 2 1 1 1 1 1 0 2 2 0 2 1 1 2 0 0 2 0 0 2 1 2 0 0 1 1 2 0 2 2 2 1 2 0 2 1 2 0 1 2 2 2 1 1 2 1 1 1 1 0 0 1 1 0 1 2 1 0 0 2 0 2 2 2 0 1 1 2 0 0 1 0 0 2 1 2 1 2 0 1 1 2 2 0 0 1 2 2 1 2 1 2 2 2 0 0 1 1 2 1 1 2 2 2 2 2 ...

output:

660
660
661
661
661
661
660
660
660
660
661
661
663
664
665
665
664
663
663
663
664
663
663
662
662
663
663
664
664
664
663
662
662
662
661
660
659
658
657
657
656
655
654
654
654
654
654
654
653
653
653
653
652
652
651
651
651
652
651
650
650
650
651
649
648
648
647
648
648
648
648
648
647
647
646
...

result:

wrong answer 3rd numbers differ - expected: '660', found: '661'

Subtask #4:

score: 0
Wrong Answer

Test #35:

score: 0
Wrong Answer
time: 1ms
memory: 9836kb

input:

2000 1999
0 1 0 3 0 1 0 0 0 0 0 0 0 2 0 0 0 0 3 1 1 0 2 0 0 3 0 0 0 0 0 4 0 0 1 0 1 0 0 0 0 1 2 1 0 0 0 0 7 0 1 3 1 0 1 1 0 3 2 1 0 1 1 3 3 1 0 2 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 1 2 3 0 1 0 3 3 0 0 0 0 1 0 1 2 0 0 2 2 0 1 2 1 2 0 0 0 1 1 0 1 2 0 0 0 0 2 0 5 0 0 0 0 0 1 0 0 2 0 1 2 0 1 0 0 0 2 0 ...

output:

666
666
666
666
665
665
665
666
666
667
666
667
667
667
667
667
667
667
667
667
670
669
668
668
667
666
665
665
664
663
663
664
663
664
663
663
663
663
661
662
661
661
661
661
658
658
657
657
657
657
657
657
656
656
656
656
656
656
656
657
657
658
659
658
656
656
656
656
656
656
656
656
655
654
654
...

result:

wrong answer 5th numbers differ - expected: '666', found: '665'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%