Submission #1272869

#TimeUsernameProblemLanguageResultExecution timeMemory
1272869goulthenLasers (NOI19_lasers)C++20
100 / 100
132 ms43760 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second

const int MAXN = 5e5+10;
const int INF = 1e18+10;

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
	int L,m;cin >> L >> m;

	vector<vector<pii>> ranges(m+1);

	rep(i,1,m) {
		int j, s=0;cin >> j;
		vector<int> a;
		while (j--) {
			int x;cin >> x;
			a.pb(x);
			s += x;
		}

		int cur = 0;
		for (int &x : a) {
			cur += x;
			if(L-s+1<=cur)ranges[i].pb({L-s+1,cur});
			s-=x;
		}
	}

	vector<pii> dif;
	rep(i,1,m) {
		for (auto &[l,r] : ranges[i]) dif.pb({l,1}), dif.pb({r+1,-1});
	}

	int lst = 0, ans = 0, cur = 0;
	sort(dif.begin(),dif.end());
	for (auto &[i, dx] : dif) {
		if (cur==0) lst = i;
		cur += dx;
		if (cur == 0) {
			ans += i-lst;
		}
	}

	cout << ans << '\n';

	return 0;
}
#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...