Submission #1268308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268308		nadeshiko	Lasers (NOI19_lasers)	C++20	0 / 100	27 ms	11072 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=0){ 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;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long Len,r;
    if(!(cin>>Len>>r)) return 0;
    BIT bit(Len+2); // <-- quan trọng: cho thêm 1-2 ô để cập nhật r+1 = Len+1
    for(long long qi=0; qi<r; qi++){
        long long n; cin>>n;
        vector<long long>a(n);
        for(long long j=0;j<n;j++) cin>>a[j];
        vector<long long> pref(n+1,0), suff(n+2,0);
        for(long long j=1;j<=n;j++) pref[j]=pref[j-1]+a[j-1];
        for(long long j=n;j>=1;j--) suff[j]=suff[j+1]+a[j-1];
        for(long long j=1;j<=n;j++){
            long long x = Len - pref[j]; // max right position
            long long y = suff[j];      // min left position
            if(x >= y){
                long long l = y+1;      // 1-based
                long long rpos = x;     // inclusive
                if(l <= rpos){
                    bit.update(l,1);
                    bit.update(rpos+1,-1); // rpos+1 may be Len+1, OK vì BIT có Len+2
                }
            }
        }
    }
    long long ans=0;
    for(long long pos=1; pos<=Len; pos++){
        if(bit.get(pos)==0) ans++;
    }
    cout<<ans<<"\n";
    return 0;
}

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