Submission #225303

#	Time	Username	Problem	Language	Result	Execution time	Memory
225303		vioalbert	Lasers (NOI19_lasers)	C++14	100 / 100	135 ms	10140 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 500005;
int k, n;
vector<pair<int, int>> seg;
int a[N];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> k >> n;
	for(int cn = 0; cn < n; cn++) {
		int x; cin >> x;
		int sumL = 0, sumR = 0;
		for(int i = 0; i < x; i++) {
			cin >> a[i];
			sumR += a[i];
		}

		for(int i = 0; i < x; i++) {
			sumR -= a[i];
			int l = sumL+1, r = k-sumR;
			int delta = (r-l+1) - a[i];
			if(l + delta <= r - delta)
				seg.push_back({l+delta, r-delta});
			sumL += a[i];
		}
	}

	sort(seg.begin(), seg.end());

	stack<pair<int, int>> st;
	for(auto& it : seg) {
		if(st.empty() || st.top().second < it.first)
			st.push(it);
		else if(it.second > st.top().second) {
			pair<int, int> u = {st.top().first, it.second};
			st.pop();
			st.push(u);
		}
	}

	int ans = 0;
	while(!st.empty()) {
		ans += st.top().second - st.top().first + 1;
		st.pop();
	}

	cout << ans << '\n';

	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