Submission #1268302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268302		vukhacminh	Lasers (NOI19_lasers)	C++20	100 / 100	98 ms	16916 KiB

lasers

/**
*    Author :  Vu Khac Minh
**/
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int maxn = 5e5 + 5;
const int mod = 1e9+7;
int len,n,a[maxn];
vector<pair<int,int>> event;
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>len>>n;
    for(int id = 1;id<=n;id++)
    {
        int x;
        cin>>x;
        int all = 0;
        for(int i = 1;i<=x;i++)
        {
            cin>>a[i];
            all+=a[i];
        }
        int pre = 0,prev = len - all+1;
        for(int i =1;i<=x;i++)
        {
            pre+=a[i];
            if(pre>=prev)
            {
                event.push_back({prev,1});
                event.push_back({pre+1,-1});
            }
            prev = len -(all-pre)+1;
        }
    }
    int m = event.size();
    ll res=0,pre=0;
    sort(event.begin(),event.end());
    for(int i = 0;i<m;i++)
    {
        int x = event[i].first,sign = event[i].second;
        pre+=sign;
        if(pre>0)
            res+=(i+1<m ? event[i+1].first - x :  len-x+1);
    }
    cout<<res;
    return 0;
}

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