This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
int qs[555555];
set<pii> s;
int main()
{
int l,q;cin>>l>>q;
while(q--)
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
qs[i]=qs[i-1];
qs[i]+=x;
}
int g=l-qs[n],r=l-qs[n]+qs[1];
if(n==1&&qs[1]>l/2)
{
s.insert({l-qs[1]+1,qs[1]});
}
for(int i=2;i<=n;i++)
{
if(g>=qs[i]-qs[i-1]) continue;
int L=r+1,R=r+qs[i]-qs[i-1]-g;
s.insert({L,R});
//cout<<r<<' '<<L<<' '<<R<<'\n';
r+=qs[i]-qs[i-1];
}
}
int cnt=0,R=0;
for(auto it=s.begin();it!=s.end();it++)
{
int u=(*it).f,v=(*it).s;
if(v<R) continue;
if(u>R)
cnt+=v-u+1;
else if(u<R)
cnt+=v-R;
R=v;
//cout<<u<<' '<<v<<'\n';
}
cout<<cnt;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |