Submission #942880

#	Time	Username	Problem	Language	Result	Execution time	Memory
942880		Lilypad	Lasers (NOI19_lasers)	C++14	100 / 100	163 ms	76216 KiB

lasers

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define pb push_back
#define fi first
#define se second

const ll N = 5e5+5;

ll l,r,xx,c,ans;
ll tot[N];
vector<ll> a[N];
vector<pii> seg[N],seg1;
stack<pii> st,st1;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> l >> r;
	for(int i=1; i<=r; i++) {
		cin >> xx;
		for(int j=1; j<=xx; j++) {
			cin >> c;
			a[i].pb(c);
			tot[i] += c;
		}
	}
	for(int i=1; i<=r; i++) {
		if(tot[i] == l) {
			cout << l << endl;
			return 0;
		}
	}
	for(int i=1; i<=r; i++) {
		ll tmp = 0;
		for(auto j : a[i]) {	
			if(tmp+1 <= l-tot[i]) seg[i].pb({tmp+1,l-tot[i]});
			tot[i] -= j;
			tmp += j;
		}
		if(tmp+1 <= l) seg[i].pb({tmp+1,l});
		sort(seg[i].begin(),seg[i].end());
		for(int j=0; j<seg[i].size(); j++) {
			pii y = seg[i][j];
			while(!st.empty()) {
				pii x = st.top();
				if(x.se < y.fi) break;
				y.fi = min(y.fi,x.fi);
				y.se = max(y.se,x.se);
				st.pop(); 
			}
			st.push(y);
		}
		ll pre = l;
		while(!st.empty()) {
			pii x = st.top();
			st.pop();
			if(x.se+1 <= pre) seg1.pb({x.se+1,pre});
			pre = x.fi-1;
		}
		if(1 <= pre) seg1.pb({1,pre}); 
	}
	sort(seg1.begin(),seg1.end());
	for(auto j : seg1) {
		pii y = j;
		while(!st1.empty()) {
			pii x = st1.top();
			if(y.se < x.fi || y.fi > x.se) break;
			y.fi = min(y.fi,x.fi);
			y.se = max(y.se,x.se);
			st1.pop(); 
		}
		st1.push(y);
	}
	while(!st1.empty()) {
		pii x = st1.top();
		st1.pop();
		ans += x.se - x.fi + 1;
	}
	cout << ans << endl;
}

Compilation message (stderr)

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

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