Submission #674747

#	Time	Username	Problem	Language	Result	Execution time	Memory
674747		QwertyPi	Lasers (NOI19_lasers)	C++14	100 / 100	391 ms	54504 KiB

lasers

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

int32_t main(){
	int l, r; cin >> l >> r;
	vector<pair<int, int>> block;
	for(int i = 0; i < r; i++){
		int k; cin >> k; int s = 0;
		vector<int> a; vector<pair<int, int>> d;
		for(int j = 0; j < k; j++){
			int v; cin >> v; a.push_back(v);
		}
		auto add = [&d, &l] (int sl, int sr){
			d.push_back({0, 1});
			d.push_back({sl, -1});
			d.push_back({l - sr, 1});
			d.push_back({l, -1});
		};
		int sl = 0, sr = accumulate(a.begin(), a.end(), 0LL);
		add(sl, sr);
		for(auto i : a){
			sl += i; sr -= i;
			add(sl, sr);
		}
		sort(d.begin(), d.end());
		int cnt = 0;
		for(auto i : d){
			cnt += i.se;
			if(cnt == k && i.se == -1) block.push_back({i.fi, -1});
			if(cnt == k + 1 && i.se == 1) block.push_back({i.fi, 1});
		}
	}
	sort(block.begin(), block.end());
	int ans = 0, cnt = 0, pv = -(1 << 30);
	for(auto i : block){
		if(cnt > 0) ans += i.fi - pv;
		cnt += i.se;
		pv = i.fi;
	}
	cout << ans << endl;
}

Compilation message (stderr)

lasers.cpp: In function 'int32_t main()':
lasers.cpp:11:24: warning: unused variable 's' [-Wunused-variable]
   11 |   int k; cin >> k; int s = 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