Submission #906449

#	Time	Username	Problem	Language	Result	Execution time	Memory
906449		starchan	Lasers (NOI19_lasers)	C++17	100 / 100	303 ms	34092 KiB

lasers

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define LMX (int)2e6+69
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
int ok(int a, int b, int c)
{
	//in [a, b] with <= c
	if(c < a)
		return 0;
	return min(b, c)-a+1;
}
struct seg_tree
{
	vector<int> tree;
	void init(int n)
	{
		tree.assign(4*n+69, 0);
		return;
	}
	void upd(int val, int pos, int id, int l, int r)
	{
		if(l == r)
		{
			tree[id] = val;
			return;
		}
		int m = (l+r)/2;
		if(pos <= m)
			upd(val, pos, 2*id, l, m);
		else
			upd(val, pos, 2*id+1, m+1, r);
		tree[id] = min(tree[2*id], tree[2*id+1]);
		return;
	}
	int rep()
	{
		return tree[1];
	}
};
signed main()
{
	fast();
	seg_tree work;
	int L, n;
	cin >> L >> n;
	work.init(n);
	vector<in> p;
	vector<int> v;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++)
	{
		int c;
		cin >> c;
		v.resize(c+1);
		v[0] = 0;
		for(int j = 1; j <= c; j++)
		{
			cin >> v[j];
			v[j]+=v[j-1];
			p.pb({v[j], i});
		}
		a[i] = L-v[c];
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)
		work.upd(a[i], i, 1, 1, n);
	sort(p.begin(), p.end());
	p.pb({L, 1});
	vector<int> upd;
	int prev = 0;
	for(auto [pr, W]: p)
	{
		if(pr > prev)
			ans+=ok(prev+1, pr, work.rep());
		prev = pr;
		work.upd(pr+a[W], W, 1, 1, n);
	}
	ans = L-ans;
	cout << ans << "\n";
	return 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