Submission #500568

#	Time	Username	Problem	Language	Result	Execution time	Memory
500568		pooty	Lasers (NOI19_lasers)	C++17	100 / 100	249 ms	44636 KiB

lasers

#define REP(i, n) for(int i = 0; i < n; i ++)
#define REPL(i,m, n) for(int i = m; i < n; i ++)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define SORT(arr) sort(arr.begin(), arr.end())
#define LSOne(S) ((S)&-(S))
#define M_PI 3.1415926535897932384
#define INF 999999999
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int l,r;cin>>l>>r;
	vvi rarr(r);
	REP(i, r) {
		int x;cin>>x;
		REP(j, x) {
			int c;cin>>c;
			rarr[i].push_back(c);
		}
	}
	set<ii> intervals;
	for (auto vec: rarr) {
		//cout<<"...\n";
		int gap = l - accumulate(vec.begin(), vec.end(), 0);
		int curright = gap;
		int curtot = 0;
		for (auto x: vec) {
			curtot += x;
			if (curtot - 1 >= curright) {
				intervals.insert({curright, curtot - 1});
				//cout<<curright<<" "<<curtot-1<<"\n";
			}
			curright = curtot + gap;
		}
	}
	int totblock = 0;
	while (!intervals.empty()) {
		auto [l,r] = *intervals.begin();
		int curl = l;
		int curr = r;
		while (!intervals.empty()) {
			auto [nl,nr] = *intervals.begin();
			if (nl <= curr) {
				intervals.erase(intervals.begin());
				curr = max(curr, nr);
			} else {
				break;
			}
		}
		totblock += (curr - curl +1);
	}
	cout<<totblock<<"\n";
}

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