제출 #1313291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313291		namhh	Lasers (NOI19_lasers)	C++20	100 / 100	107 ms	8480 KiB

lasers

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 5e5+5;
int l,r,a[N];
vector<pii>doan;
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> l >> r;
	for(int i = 1; i <= r; i++){
		int x;
		cin >> x;
		int sum = 0;
		for(int j = 1; j <= x; j++){
			cin >> a[j];
			sum += a[j];
		}
		a[x+1] = 0;
		int le = sum;
		vector<pii>loj;
		for(int j = x+1; j >= 1; j--){
			le -= a[j];
			int ri = l-(sum-le);
			if(le <= ri) loj.push_back({le+1,ri});
		}
		if(loj.empty()) continue;
		sort(loj.begin(),loj.end());
		vector<pii>chon;
		chon.push_back({0,0});
		le = loj[0].fi;
	    int ri = loj[0].se;
	    for(int j = 1; j < loj.size(); j++){
		    if(ri >= loj[j].fi){
			    le = min(le,loj[j].fi);
			    ri = max(ri,loj[j].se);
		    }
	     	else{
	     	    chon.push_back({le,ri});
	    		le = loj[j].fi;
	    		ri = loj[j].se;
	    	}
    	}
    	chon.push_back({le,ri});
    	chon.push_back({l+1,l+1});
    	for(int j = 1; j < chon.size(); j++){
    		if(chon[j].fi > chon[j-1].se+1) doan.push_back({chon[j-1].se+1,chon[j].fi-1});
		}
	}
	if(doan.empty()){
		cout << 0;
		return 0;
	}
	sort(doan.begin(),doan.end());
	int ans = 0;
	int le = doan[0].fi;
	int ri = doan[0].se;
	for(int i = 1; i < doan.size(); i++){
		if(ri >= doan[i].fi){
			le = min(le,doan[i].fi);
			ri = max(ri,doan[i].se);
		}
		else{
			ans += (ri-le+1);
			le = doan[i].fi;
			ri = doan[i].se;
		}
	}
	ans += (ri-le+1);
	cout << ans;
}

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