Submission #1268309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268309		nadeshiko	Lasers (NOI19_lasers)	C++20	0 / 100	47 ms	10816 KiB

lasers

#include <bits/stdc++.h>

using namespace std;
struct BIT
{
    long long n;
    vector<long long>bit;
    void init(long long _n)
    {
        n=_n;
        bit.assign(n+1,0);
    }
    BIT(long long n)
    {
        init(n);
    }
    void update(long long id,long long val)
    {
        for(; id<=n; id+=id&-id)
        {
            bit[id]+=val;
        }
    }
    long long get(long long id)
    {
        long long sum=0;
        for(; id>0; id-=id&-id)
        {
            sum+=bit[id];
        }
        return sum;
    }
    long long query(long long l,long long r)
    {
        return get(r)-get(l-1);
    }
};
int main()
{
    long long Len,r;
    cin>>Len>>r;
    //Len--;
    BIT bit(Len+2);
    for(int i=0; i<r; i++)
    {
        long long n;
        cin>>n;
        vector<long long>a(n);
        for(int i=0; i<n; i++)cin>>a[i];
        vector<long long>pref(n+1,0);
        vector<long long>suff(n+2,0);
        for(int i=1; i<=n; i++)
        {
            pref[i]=pref[i-1]+a[i-1];
        }
        for(int i=n; i>=1; i--)
        {
            suff[i]=suff[i+1]+a[i-1];
        }
        for(int i=1; i<=n; i++)
        {
            long long x=Len-pref[i];
            long long y=suff[i];
            if(x >= y){
                long long l=y+1;
                long long rpos=x;
                if(l<=rpos){
                    bit.update(l,1);
                    bit.update(rpos+1,-1);
                }
            }
        }
    }
    long long ans=0;
    for(int i=0; i<Len; i++)
    {
        if(bit.get(i+1)==0)
        {
            ans++;
        }
    }
    cout<<ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 21
• Subtask 5: 0 / 22
• Subtask 6: 0 / 13