Submission #1268306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268306		nadeshiko	Lasers (NOI19_lasers)	C++20	0 / 100	147 ms	327680 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
struct BIT{
    int n; vector<int> b;
    void init(int _n){ n=_n; b.assign(n+1,0); }
    BIT(int _n=0){ init(_n); }
    void upd(int id,int v){ for(; id<=n; id+=id&-id) b[id]+=v; }
    int get(int id){ int s=0; for(; id>0; id-=id&-id) s+=b[id]; return s; }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int L,R; if(!(cin>>L>>R)) return 0;
    BIT bit(L+5); // +5 cho an toàn vì ta sẽ cập nhật tới x+1
    for(int t=0; t<R; t++){
        int m; cin>>m;
        vector<int>a(m);
        for(int i=0;i<m;i++) cin>>a[i];
        vector<int> pref(m+1,0), suff(m+2,0);
        for(int i=1;i<=m;i++) pref[i]=pref[i-1]+a[i-1];
        for(int i=m;i>=1;i--) suff[i]=suff[i+1]+a[i-1];
        for(int i=1;i<=m;i++){
            int x = L - pref[i];
            int y = suff[i];
            // khoảng dịch p thỏa (p in [y .. x-1])  (0-based p)
            if(x>y){ // nếu x==y thì khoảng rỗng
                // ánh xạ sang BIT 1-based: p -> p+1
                bit.upd(y+1,1);
                bit.upd(x+1,-1);
            }
        }
    }
    long long ans=0;
    for(int p=0;p<L;p++){
        if(bit.get(p+1)==0) ans++;
    }
    cout<<ans<<"\n";
}

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