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 ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>
#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define x first
#define y second
#define mp make_pair
#define pb push_back
const ll N = 5e5+5, MOD = 1e9+7;
ll tc = 1, n, m, ar[N], br[N];
ll k, len;
string s, s1, s2, ye = "YA", no = "TIDAK";
map<ll,ll> mapz;
vector<ll> v;
vector<pairll> cmp;
void input(){
cin >> len >> n;
repp(j,1,n){
//cout << "i = " << j << endl;
cin >> k;
v.clear();
cmp.clear();
ll rig = 0, lef = 0;
while(k--){
cin >> m;
v.pb(m);
rig += m;
}
for (auto i : v){
cmp.pb(mp(lef+1,len-rig));
rig -= i;
lef += i;
}
cmp.pb(mp(lef+1,len));
ll l = cmp[0].fr, r = cmp[0].sc;
for (auto i : cmp){
//cout << i.fr << " " << i.sc << endl;
if (i.fr > r){
mapz[l]++;
mapz[r+1]--;
//cout << l << " " << r << endl;
l = i.fr;
r = i.sc;
}
else r = max(r,i.sc);
}
mapz[l]++;
mapz[r+1]--;
//cout << l << " " << r << endl;
}
}
void solve(){
ll ans = 0, cur = 0, pre = -1;
for (auto it = mapz.begin(); it != mapz.end(); ++it){
ll key = it -> first, val = it->second;
cur += val;
//cout << "mapz = " << key << " " << cur << endl;
if (cur < n && pre != -1){
ans += key-pre;
//cout << key << " " << pre << endl;
pre = -1;
}
else if (pre == -1 && cur == n) pre = key;
}
cout << len-ans << endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//cin >> tc;
while(tc--){
input();
solve();
}
}
# | 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... |