Submission #1268292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268292		phamminhson	Lasers (NOI19_lasers)	C++20	45 / 100	68 ms	8008 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
const int N = 500005;
pll segs[N];
int nseg=0;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll L; int R; if(!(cin>>L>>R)) return 0;
    while(R--){
        int X; cin>>X;
        static ll a[1005];
        ll total=0;
        for(int i=1;i<=X;i++){ cin>>a[i]; total+=a[i]; }
        ll S = L - total, P = 0;
        for(int i=1;i<=X;i++){
            ll l = P + S + 1, r = P + a[i];
            if(l<1) l=1; if(r> L) r=L;
            if(l<=r) segs[++nseg] = {l,r};
            P += a[i];
        }
    }
    if(!nseg){ cout<<0; return 0; }
    sort(segs+1, segs+nseg+1);
    ll ans=0, Lc=segs[1].first, Rc=segs[1].second;
    for(int i=2;i<=nseg;i++){
        if(segs[i].first>Rc){
            ans += Rc - Lc + 1;
            Lc = segs[i].first; Rc = segs[i].second;
        } else Rc = max(Rc, segs[i].second);
    }
    ans += Rc - Lc + 1;
    cout<<ans;
    return 0;
}

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