Submission #1012934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012934		xnqs	Lasers (NOI19_lasers)	C++17	0 / 100	58 ms	10620 KiB

lasers

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>

int x, q;

std::vector<std::pair<int,int>> can_uncover(int n, int l, int offset) {
	std::vector<std::pair<int,int>> ret;
	if (l <= n/2) {
		ret.emplace_back(1,n);
	}
	else if (l < n) {
		ret.emplace_back(1,n-l);
		ret.emplace_back(n-(n-l)+1,n);
	}

	for (auto& [i, j] : ret) {
		i += offset;
		j += offset;
	}

	return ret;
}

std::vector<std::pair<int,int>> union_segments(std::vector<std::pair<int,int>> arr) {
	std::sort(arr.begin(),arr.end());

	std::vector<std::pair<int,int>> ret;
	for (const auto& [l, r] : arr) {
		if (ret.empty()||ret.back().second<l) {
			ret.emplace_back(l,r);
		}
		else {
			ret.back().second = std::max(ret.back().second,r);
		}
	}

	return ret;
}

std::vector<std::pair<int,int>> not_segments(std::vector<std::pair<int,int>> arr) {
	std::sort(arr.begin(),arr.end());

	std::vector<std::pair<int,int>> ret;
	if (arr[0].first>1) {
		ret.emplace_back(1,arr[0].first-1);
	}
	for (int i = 0; i < arr.size()-1; i++) {
		if (arr[i+1].first-arr[i].second>1) {
			ret.emplace_back(arr[i].second+1,arr[i+1].first-1);
		}
	}
	if (x-arr.back().second>=1) {
		ret.emplace_back(arr.back().second+1,x);
	}

	return ret;
}

int sum_segments(const std::vector<std::pair<int,int>>& arr) {
	int ret = 0;
	for (const auto& [l, r] : arr) {
		ret += r-l+1;
	}
	return ret;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	std::cin >> x >> q;

	std::vector<std::pair<int,int>> segments_covered;
	while (q--) {
		int n;
		std::cin >> n;

		std::vector<int> walls(n);
		for (auto& i : walls) {
			std::cin >> i;
		}

		int pfx = 0, sfx = std::accumulate(walls.begin(),walls.end(),0);
		std::vector<std::pair<int,int>> segments_uncovered;
		for (int i = 0; i < n; i++) {
			auto tmp = can_uncover(x-pfx,sfx,pfx);
			for (const auto& it : tmp) {
				segments_uncovered.emplace_back(it);
			}

			pfx += walls[i];
			sfx -= walls[i];
		}

		auto neg = not_segments(union_segments(segments_uncovered));
		for (const auto& it : neg) {
			segments_covered.emplace_back(it);
		}
	}

	segments_covered = union_segments(segments_covered);
	std::cout << sum_segments(segments_covered) << "\n";
}

Compilation message (stderr)

lasers.cpp: In function 'std::vector<std::pair<int, int> > not_segments(std::vector<std::pair<int, int> >)':
lasers.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < arr.size()-1; i++) {
      |                  ~~^~~~~~~~~~~~~~

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