Submission #333024

#	Time	Username	Problem	Language	Result	Execution time	Memory
333024		guka415	Lasers (NOI19_lasers)	C++14	100 / 100	319 ms	10004 KiB

lasers

#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int sz = 5e5+5;
ll l, n;
vector<pair<int, bool>> segs;

inline bool intersect(const pii& lhs, const pii& rhs) {
	return (rhs.first - lhs.second <= 1);
}


int main() {
	fast;
	cin >> l >> n;
	bool bad = 0;
	while (n--) {
		vector<int> v;
		int x, tmp, rsum = 0, lsum = 0;
		cin >> x;
		foru(i, 0, x) {
			cin >> tmp;
			rsum += tmp;
			v.pb(tmp);
		}
		if (rsum == l) {
			bad = 1;
			continue;
		}
		vector<pii> yes;
		yes.pb({ 0,l - rsum - 1 });
		lsum += v[0];
		rsum -= v[0];
		foru(i, 1, x + 1) {
			pii inval = { lsum, l - rsum - 1 }, yb = yes.back();
			if (intersect(yb, inval)) {
				yes.back() = { yb.first,inval.second };
			}
			else {
				yes.pb(inval);
			}
			if (i != x) {
				lsum += v[i];
				rsum -= v[i];
			}
		}
		foru(i, 0, yes.size() - 1) {
			segs.pb({ yes[i].second + 1,0 });
			segs.pb({ yes[i + 1].first - 1,1 });
		}
	}
	if (bad) {
		cout << l << '\n';
		return 0;
	}
	sort(segs.begin(), segs.end());
	ll tot = 0, prvLit = -1;
	int o = 0;
	for (auto x : segs) {
		if (!x.second) {
			if (o == 0) {
				prvLit = x.first;
			}
			o++;
		}
		else {
			o--;
			if (o == 0) {
				tot += (x.first - prvLit + 1);
			}
		}
	}
	cout << tot << '\n';
	return 0;
}

Compilation message (stderr)

lasers.cpp: In function 'int main()':
lasers.cpp:2:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define foru(i, k, n) for (int i = k; i < n; i++)
......
   62 |   foru(i, 0, yes.size() - 1) {
      |        ~~~~~~~~~~~~~~~~~~~~              
lasers.cpp:62:3: note: in expansion of macro 'foru'
   62 |   foru(i, 0, yes.size() - 1) {
      |   ^~~~

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