Submission #901353

#	Time	Username	Problem	Language	Result	Execution time	Memory
901353		pcc	Lasers (NOI19_lasers)	C++14	100 / 100	259 ms	28200 KiB

lasers

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e6+10;

ll R,L;
int arr[mxn];
vector<pii> range;
vector<int> all;

void GO(){
	int n;
	cin>>n;
	int arr[n];
	int ls = 0,rs = 0;
	for(auto &i:arr){
		cin>>i;
		rs += i;
	}
	vector<pll> v;
	for(auto &i:arr){
		v.push_back({ls+1,L-rs+1});
		ls += i;
		rs -= i;
	}
	v.push_back({ls+1,L-rs+1});
	vector<pll> tmp;
	for(auto &i:v){
		if(tmp.empty()||tmp.back().sc<i.fs)tmp.push_back(i);
		else tmp.back().sc = max(i.sc,tmp.back().sc);
	}
	for(auto &i:tmp)range.push_back(i);
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>L>>R;
	for(int i = 0;i<R;i++)GO();
	for(auto &i:range){
		all.push_back(i.fs);
		all.push_back(i.sc);
	}
	sort(all.begin(),all.end());
	all.resize(unique(all.begin(),all.end())-all.begin());
	for(auto &i:range){
		int l = lower_bound(all.begin(),all.end(),i.fs)-all.begin();
		int r = lower_bound(all.begin(),all.end(),i.sc)-all.begin();
		arr[l]++;
		arr[r]--;
	}
	int ans = L;
	int tsum = 0;
	for(int i = 0;i<all.size();i++){
		tsum += arr[i];
		if(tsum == R)ans -= all[i+1]-all[i];
	}
	cout<<ans;
}

Compilation message (stderr)

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

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