Submission #1151224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151224		altern23	Lasers (NOI19_lasers)	C++20	0 / 100	37 ms	10504 KiB

lasers

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

#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
 
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sec second
#define ld long double

ostream& operator << (ostream& os, pii x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<pii, ll> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<ll, pii> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

template <typename T>
ostream& operator << (ostream& os, vector<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}

template <typename T>
ostream& operator << (ostream& os, set<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}
 
template <typename T>
ostream& operator << (ostream& os, multiset<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}

const ll MOD = 1e9 + 7;
const ll N = 1e5;
const ll INF = 2e18;

// modulo operations
void add(ll &a, ll b) { a = (a + b) % MOD; while(a < 0) a += MOD; a %= MOD; }
void sub(ll &a, ll b) { a -= b; while(a < 0) a += MOD; a %= MOD; }
void mul(ll &a, ll b) { a = (a * b) % MOD; }

ll expo(ll a, ll b) {
    ll ans = 1;
    while(b > 0){
        if(b & 1) mul(ans, a);
        mul(a, a);
        b /= 2;
    }

    return ans;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll l, r; cin >> l >> r;
        auto line_sweep = [&](vector<pii> &tmp){
            ll lf = -1, rg = -1;
            sort(tmp.begin(), tmp.end());
            vector<pii> res;
            for(auto [L, R] : tmp){
                if(rg < L){
                    if(lf != -1) res.push_back({lf, rg});
                    lf = L, rg = R;
                }
                else rg = max(rg, R);
            }
            if(lf != -1) res.push_back({lf, rg});
            return res;
        };

        vector<pii> ans;
        for(int i = 1; i <= r; i++){
            ll x; cin >> x;
            vector<ll> b(x + 5);
            for(int j = 1; j <= x; j++) cin >> b[j];

            ll sum = accumulate(b.begin() + 1, b.begin() + 1 + x, 0LL);
            ll res = l - sum;

            if(res == 0) continue;

            vector<pii> tmp;
            ll L = 1;
            for(int j = 1; j <= x; j++){
                tmp.push_back({L, L + res - 1});
                L += b[j];
            }
            tmp.push_back({L, L + res - 1});

            tmp = line_sweep(tmp);
            sort(tmp.begin(), tmp.end());
            L = 1;
            for(auto [ki, ka] : tmp){
                if(L <= ki - 1) ans.push_back({L, ki - 1});
                L = ka + 1;
            }
            if(L <= l) ans.push_back({L, l});
        }

        ans = line_sweep(ans);
        ll tot = 0;
        for(auto [L, R] : ans) tot += R - L + 1;

        cout << tot << "\n";
    }   
}

/*

*/  

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