Submission #501079

#	Time	Username	Problem	Language	Result	Execution time	Memory
501079		arujbansal	Lasers (NOI19_lasers)	C++17	100 / 100	457 ms	74840 KiB

lasers

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

const int INF = 1e9 + 5;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, R;
	cin >> N >> R;

	vector<int> walls[R];
	for (int i = 0; i < R; i++) {
		int k;
		cin >> k;

		walls[i].resize(k + 2);
		walls[i][0] = walls[i][k + 1] = 0;
		for (int j = 1; j <= k; j++)
			cin >> walls[i][j];
	}

	unordered_map<int, int> diff_mp;

	for (int i = 0; i < R; i++) {
		vector<int> pref(sz(walls[i]), 0);
		vector<pair<int, int>> ranges, merged_ranges;

		for (int j = 1; j < sz(walls[i]); j++)
			pref[j] = walls[i][j] + pref[j - 1];

		for (int j = 0; j < sz(walls[i]) - 1; j++) {
			int l = pref[j] + 1;
			int r = N - (pref.back() - pref[j]);

			if (l <= r) ranges.emplace_back(l, r);
		}

		ranges.emplace_back(INF, INF);

		int cur_l = -1, cur_r = -1;
		for (const auto &[l, r] : ranges) {
			if (l > cur_r) {
				if (cur_l > -1) merged_ranges.emplace_back(cur_l, cur_r);
				cur_l = l, cur_r = r;
			} else cur_r = max(cur_r, r);
		}

		for (const auto &[l, r] : merged_ranges) {
			// cout << l << " " << r << "\n";
			diff_mp[l]++;
			diff_mp[r + 1]--;
		}

		// cout << "\n\n";
	}

	vector<pair<int, int>> diff;
	for (const auto [k, v] : diff_mp) {
		diff.emplace_back(k, v);
		diff.emplace_back(k - 1, 0);
		diff.emplace_back(k + 1, 0);
	}

	sort(all(diff));

	int total = 0;

	for (int i = 2; i < sz(diff); i++)
		diff[i].second += diff[i - 1].second;

	for (int i = 1; i < sz(diff); i++) {
		bool move = false;

		if (diff[i].second == R) {
			int extend = diff[i].first;
			total -= extend - 1;

			while (i < sz(diff) - 1) {
				i++;
				move = true;
				if (diff[i].second != R) break;
				extend = diff[i].first;
			}

			total += extend;
		}

		
		i -= move;
	}

	cout << N - total;
}

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