Submission #645389

#	Time	Username	Problem	Language	Result	Execution time	Memory
645389		gun_gan	Lasers (NOI19_lasers)	C++17	0 / 100	78 ms	48064 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5e5 + 5;
int l, r, curr[N], sum[N];
vector<int> s[2 * N], pt;
multiset<int> S;
 
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
 
	cin >> l >> r;
	int ans = 0;
	for(int i = 0; i < r; i++) {
		int x; cin >> x;
		for(int j = 0; j < x; j++) {
			int p; cin >> p;
			sum[i] += p;
			s[sum[i]].push_back(i);
			pt.push_back(sum[i]);
		}
		S.insert(sum[i]);
	}
	sort(pt.begin(), pt.end());
	pt.erase(unique(pt.begin(), pt.end()), pt.end());

	int last = 0;
	for(auto x : pt) {
		if(l - x < *S.rbegin()) ans += x - last;
		for(auto j : s[x]) {
			S.erase(S.find(sum[j] - curr[j]));
			curr[j] = x;
			S.insert(sum[j] - curr[j]);
		}
		last = x;
	}
	cout << ans << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 21
• Subtask 5: 0 / 22
• Subtask 6: 0 / 13