Submission #224521

#	Time	Username	Problem	Language	Result	Execution time	Memory
224521		kshitij_sodani	Lasers (NOI19_lasers)	C++17	100 / 100	189 ms	35308 KiB

lasers

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long int llo;
llo mod=1000000007;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int l,r;
	cin>>l>>r;
	int x;
	vector<int> aa[r];
	int y;
	for(int i=0;i<r;i++){
		cin>>x;
		for(int j=0;j<x;j++){
			cin>>y;
			aa[i].pb(y);
		}
	}
	vector<pair<int,int>> ran;
	for(int i=0;i<r;i++){
		if(aa[i].size()==0){
			continue;
		}
		int pre[aa[i].size()];
		int ss[aa[i].size()];
		pre[0]=aa[i][0];
		for(int j=1;j<aa[i].size();j++){
			pre[j]=pre[j-1]+aa[i][j];
		}
		ss[aa[i].size()-1]=aa[i][aa[i].size()-1];
		for(int j=aa[i].size()-2;j>=0;j--){
			ss[j]=ss[j+1]+aa[i][j];
		}
		for(int j=0;j<aa[i].size();j++){
			int st=0;
			int e=aa[i][0]-1;
			if(j>0){
				st=pre[j-1];
				e=st+aa[i][j]-1;
			}
			int st2=l-ss[j];
			int e2=st2+aa[i][j]-1;
			if(e>=st2){
				ran.pb({st2,e});

			}
		}
	}
	sort(ran.begin(),ran.end());
	int ans=0;
	int mi=-1;
	int ma=-1;
	for(auto nn:ran){
	//	cout<<nn.a<<" "<<nn.b<<endl;
		if(nn.a>ma){
			if(ma!=-1){
				ans+=ma-mi+1;
			}
			mi=nn.a;
			ma=nn.b;
			
		}
		else{
			ma=max(ma,nn.b);
		}
	}
	if(ma!=-1){
		ans+=ma-mi+1;
	}	
	cout<<ans<<endl;
	return 0;
}

Compilation message (stderr)

lasers.cpp: In function 'int main()':
lasers.cpp:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<aa[i].size();j++){
               ~^~~~~~~~~~~~~
lasers.cpp:39:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<aa[i].size();j++){
               ~^~~~~~~~~~~~~
lasers.cpp:47:8: warning: unused variable 'e2' [-Wunused-variable]
    int e2=st2+aa[i][j]-1;
        ^~

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