Submission #238513

#	Time	Username	Problem	Language	Result	Execution time	Memory
238513		Pbezz	Lasers (NOI19_lasers)	C++14	100 / 100	507 ms	60536 KiB

lasers

#include <bits/stdc++.h>
using namespace std;

#define loop(i,n) for (ll i = 0; i < n; i++)

#define ll long long
#define INF 1e9+5
#define MAXN 300007
#define pb push_back 
#define mp make_pair
typedef pair<ll,ll> pii;


int main(){

	ll l,r,i,j,k,x,maxi=0;
	cin>>l>>r;

	vector<vector<ll>>row(r);
	vector<vector<ll>>dp(r); 

	for(i=0;i<r;i++){

	cin>>x;
	maxi=max(maxi,x);
	dp[i].pb(0);

	for(j=1;j<=x;j++){
	cin>>k;
	row[i].pb(k);
	dp[i].pb(dp[i][j-1]+k);
	}

}

	if(maxi==1){//só há um por linha

	ll savedL=INF, savedR=-1;

	for(i=0;i<r;i++){

	k=row[i][0];

	savedR = max(savedR , k);

	savedL = min(savedL, l-k-1);

}

	k = savedL+1;

	savedR=max(savedR,savedL+1);
	k+=(l-savedR);
	printf("%lld\n",l-k);


	}else{
	ll left, right,m,cur=0;


	vector<pii>overall;

	for(i=0;i<r;i++){
	m=dp[i][dp[i].size()-1];
	vector<pii>intervals;

	if(m==l){
	cout<<l<<'\n';
	return 0;
}

	for(j=0;j<(ll)dp[i].size();j++){

		left=dp[i][j]+1;
		right=l-(m-left)-1;

		if(left>right)continue;

		intervals.pb({ left,1 });
		intervals.pb({ right+1,-1 });//a partir de right, não está safe

	}
	sort(intervals.begin(),intervals.end());

	for(j=0;j<(ll)intervals.size();j++){

		cur+=intervals[j].second;

		while(j+1<(ll)intervals.size() && intervals[j+1].first==intervals[j].first){
		j++;
		cur+=intervals[j].second;
		}

		if(cur==0){
	//a partir desta posição, os lasers foram apanhados em todas as configurações

		if(j==(ll)intervals.size()-1){
		overall.pb({ intervals[j].first, 1 });
		overall.pb({ l+1, -1 });
		}else{
		overall.pb({ intervals[j].first, 1 });
		overall.pb({ intervals[j+1].first, -1 });
		}


		}

	}


}
	sort(overall.begin(),overall.end());

/*
	for(j=0;j<(ll)overall.size();j++){
		cout<<overall[j].first<<" "<<overall[j].second<<"   ";}
cout<<endl;*/

	cur=0; ll ans=0;
	for(i=0;i<(ll)overall.size();i++){

		if(overall[i].first==l+1)break;

		cur+=overall[i].second;

		while(i<(ll)overall.size()-1 && overall[i+1].first==overall[i].first){

		i++;
		cur+=overall[i].second;

		}

		if(cur>0){

		ans+=(overall[i+1].first-overall[i].first);
		

	}

}

	cout<<ans<<endl;


}
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