제출 #1321193

#제출 시각아이디문제언어결과실행 시간메모리
1321193Roumak77Lasers (NOI19_lasers)C++17
100 / 100
249 ms17136 KiB
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


void m(vector<pair<ll, ll>> &f, vector<pair<ll, ll>> &ret){
    
    if(f.size() == 0){
        return;
    }
    
    ret.push_back(f[0]);
    ll n = f.size();
    
    for(ll i = 1; i < n; i++){
        auto l = ret.back();
        auto p = f[i];
        
        
        if(p.first > l.second){
            ret.push_back({p.first, p.second});
            continue;
        }
        
        if(l.second >= p.first){
            ret.back().second = max(l.second, p.second);
        }
        
        
    }
    
    
}


int main() {
	
	ll n, r;
	cin >> n >> r;
	
	vector<pair<ll, ll>> blocked;
	
	for(ll line_blocker = 0; line_blocker < r; line_blocker++){
	    
	    ll number_of_segments = 0;
	    cin >> number_of_segments;
	    ll total_sum = 0;
	    
	    ll curr_sum = 0;
	    
	    vector<ll> segments(number_of_segments, 0);
	    for(ll _ = 0; _ < number_of_segments; _++){
	        cin >> segments[_];
	        total_sum += segments[_];
	    }
	    
	    ll rem = n - total_sum - 1;

	    
	    vector<pair<ll, ll>> segments_range;
	    
	    for(ll i = 0; i < number_of_segments; i++){
	        
	       segments_range.push_back({curr_sum, rem});
	       
	       curr_sum += segments[i];
	       rem += segments[i];
	        
	    }
	    
	    segments_range.push_back({curr_sum, rem});

	  
	  
	    vector<pair<ll, ll>> ret;
	    
	    
	    
	    m(segments_range, ret);
	    
	   
	    
	    ll last = 0;
	    for(auto i : ret){
	        //cout << i.first << " " << i.second << " " << last << endl;
	        if(i.first <= last){
	            last = i.second + 1;
	            continue;
	        }
	        
	        blocked.push_back({last, i.first - 1});
	        last = i.second + 1;
	    }
	    
	    if(last < n - 1){
	        blocked.push_back({last, n - 1});
	    }
	    
	    //cout << "done" << endl;
	    
        
	    
	}
	
	 /*for(auto i : blocked){
	        cout << i.first << " " << i.second << endl;
	 }
	    
	 cout << "lol" << endl;*/
	 
	 vector<pair<ll, ll>> ret;
	 ll t = 0;
	 
	 if(blocked.size() >= 1){
	     sort(blocked.begin(), blocked.end());
	    m(blocked, ret);
	    for(auto i : ret){
	     t += i.second - i.first + 1;
	 }
	 }
	 
	 

	 
	 cout << t << endl;
	
	
	

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...