Submission #815858

#	Time	Username	Problem	Language	Result	Execution time	Memory
815858		christinelynn	Lasers (NOI19_lasers)	C++17	100 / 100	249 ms	39252 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 5e5 + 5;

int x[N], sum[N];
vector<int> a[N];
vector<pair<int, int>> v, ans1, ans2;

int main() { 
    //ios_base::sync_with_stdio(false); cin.tie(NULL);
    int l, r;
    cin >> l >> r;
    for (int i = 1; i <= r; i++) {
        cin >> x[i];
        for (int j = 0; j < x[i]; j++) {
            int x2;
            cin >> x2;
            a[i].push_back(x2);
            sum[i] += x2;
        }
    }
    for (int i = 1; i <= r; i++) {
        v.clear();
        if (sum[i] == l) {
            ans1.push_back({1, l});
            break;
        }
        int sum1 = 0, sum2 = sum[i];
        v.push_back({sum1 + 1, l - sum2});
        for (int j = 0; j < x[i]; j++) {
            sum1 += a[i][j], sum2 -= a[i][j];
            v.push_back({sum1 + 1, l - sum2});
        }
        for (int j = 1; j < (int)v.size(); j++) {
            if (v[j].fi <= v[j - 1].se) continue;
            ans1.push_back({v[j - 1].se + 1, v[j].fi - 1});
        }
        // cout << i << "flaw\n";
        // for (auto j : v) cout << j.fi << " " << j.se << "fkwoa\n";
    }
    sort(ans1.begin(), ans1.end());
    // for (auto i : ans1) cout << i.fi << " " << i.se << "dkawop\n";
    for (auto y : ans1) {
        if (ans2.empty()) ans2.push_back(y);
        else {
            if (y.fi <= ans2.back().se) ans2.back().se = max(ans2.back().se, y.se);
            else ans2.push_back(y);
        }
    }
    int ans = 0;
    for (auto y : ans2) ans += y.se - y.fi + 1;
    cout << ans << "\n";
}  

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