Submission #998715

#TimeUsernameProblemLanguageResultExecution timeMemory
998715adkjtLasers (NOI19_lasers)C++14
24 / 100
252 ms14792 KiB
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define f first #define s second int qs[555555],a[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]) { r=qs[i]+g; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...