제출 #1361660

#제출 시각아이디문제언어결과실행 시간메모리
1361660orucLasers (NOI19_lasers)C++20
63 / 100
82 ms8768 KiB
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define endl '\n'

const int INF = 0x3f3f3f3f3f3f3f3f, MOD = 1e9+7, LOG = 20, N = 2e5+5;


void solve(){
    int n,m; cin >> n >> m;
    int ans = 0;
    vector<pair<int,int>> res;
    for(int i = 1; i <= m; i++){
        int l; cin >> l;
        int tot = 0;
        vector<int> pr(l+1);
        for(int j = 1; j <= l; j++){
            int x; cin >> x;
            tot += x;
            pr[j] = pr[j-1] + x;
        }
        vector<pair<int,int>> v;
        for(int i = 0; i <= l; i++){
            v.push_back({pr[i]+1, n - (tot-pr[i])});
        }
        sort(v.begin(), v.end());
        
        
        vector<pair<int,int>> inter;
        inter.push_back({0,0});
        int mnl = v[0].first, mxr = v[0].second;
        for(int i = 1; i < v.size(); i++){
            if(v[i].first > mxr){
                inter.push_back({mnl,mxr});
                mnl = v[i].first;
                mxr = v[i].second;
            }
            else{
                mnl = min(mnl, v[i].first);
                mxr = max(mxr, v[i].second);
            }
        }
        inter.push_back({mnl,mxr});
        inter.push_back({n+1,n+1});
        for(int i = 1; i < inter.size(); i++){
            if(inter[i-1].second == inter[i].first-1) continue;
            res.push_back({inter[i-1].second+1, inter[i].first-1});
        }
    }
    
    sort(res.begin(), res.end());
    vector<pair<int,int>> son;
    int mnl = res[0].first, mxr = res[0].second;
    for(int i = 1; i < res.size(); i++){
        if(res[i].first > mxr){
            son.push_back({mnl,mxr});
            mnl = res[i].first;
            mxr = res[i].second;
        }
        else{
            mnl = min(mnl, res[i].first);
            mxr = max(mxr, res[i].second);
        }
    }
    son.push_back({mnl,mxr});
    for(auto [a,b] : son){
        ans += (b-a+1);
    }
    cout << ans << endl;
}

/*
    5,6
    7
    3,4,5,6,7,9
*/

signed main(){  
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    // cin >> t;
    for(int i = 1; i <= t; i++){
        solve();
    }
}          

컴파일 시 표준 에러 (stderr) 메시지

lasers.cpp:6:17: warning: overflow in conversion from 'long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
    6 | const int INF = 0x3f3f3f3f3f3f3f3f, MOD = 1e9+7, LOG = 20, N = 2e5+5;
      |                 ^~~~~~~~~~~~~~~~~~
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…