제출 #1301272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301272		hypersphere	Lasers (NOI19_lasers)	C++20	0 / 100	28 ms	7372 KiB

lasers

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

#define ll long long
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

const ll INF = 1e18;
const ll mod = 1e9 + 7;

ll binpow(ll base, ll exp, ll mod) {
    ll ans = 1;
    ll mult = base;
    while(exp) {
        if(exp & 1) ans = (ans * mult) % mod;
        mult = (mult * mult) % mod;
        exp >>= 1;
    }
    return ans;
} 

ll gcd(ll a, ll b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}

void solve() {
    int L, R;
    cin >> L >> R;

    vector<pair<ll, ll>> blockable;
    for(int i = 0; i < R; i++) {
        int n; cin >> n;
        vector<ll> pref(n + 1, 0);
        int sum = 0;
        for(int i = 1; i <= n; i++) {
            cin >> pref[i];
            sum += pref[i];
            pref[i] += pref[i-1];
        }

        if(sum == L) continue;

        int l = -1;
        int r = -1;
        vector<pair<int, int>> free_segments;
        for(int i = 0; i <= n; i++) {
            int left_free = pref[i] + 1;
            int right_free = L - (pref[n] - pref[i]);

            if(l == -1) {
                l = left_free;
                r = right_free;
            } else if(left_free <= r+1) {
                r = right_free;
            } else {
                free_segments.push_back({l, r});
                l = left_free;
                r = right_free;
            }
        }
        free_segments.push_back({l, r});

        for(int i = 0; i < (int)free_segments.size() - 1; i++) {
            int l = free_segments[i].second + 1;
            int r = free_segments[i+1].first - 1;
            blockable.push_back({l, r});
        }
    }
    sort(blockable.begin(), blockable.end());
    int guaranteed_block = 0;

    int l = 0;
    int r = -1;
    for(int i = 0; i < blockable.size(); i++) {
        if(l == -1) {
            l = blockable[i].first;
            r = blockable[i].second;
        } else if(blockable[i].first <= r+1) {
            r = blockable[i].second;
        } else {
            guaranteed_block += (r-l+1);
            l = blockable[i].first;
            r = blockable[i].second;
        }
    }

    guaranteed_block += (r-l+1);
    cout << guaranteed_block << "\n";
}

int main() {
    //freopen("COLLECT.INP", "r", stdin);
    //freopen("COLLECT.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tests = 1;
    //cin >> tests;

    while(tests--) solve();
}

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