Submission #1301250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301250		BuiDucManh123	Lasers (NOI19_lasers)	C++20	100 / 100	90 ms	29616 KiB

lasers

#pragma optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define TN ""
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int x[500009];
vector<int> a[500009];
set<pair<int, int>> st;
void add(int l, int r){
    auto it = st.lower_bound({l, INT_MIN});
    if (it != st.begin()) {
        auto prev = it;
        --prev;
        if (prev->second >= l) {
            l = min(l, prev->first);
            r = max(r, prev->second);
            st.erase(prev);
        }
    }

    it = st.lower_bound({l, INT_MIN});
    while (it != st.end() && it->first <= r) {
        r = max(r, it->second);
        it = st.erase(it);
    }

    st.insert({l, r});
}
void Solve(){
    int l, r;
    cin >> l >> r;
    for(int i = 1; i <= r; i++){
        cin >> x[i];
        a[i].resize(x[i] + 1, 0);
        for(int j = 1; j <= x[i]; j++){
            cin >> a[i][j];
            a[i][j] += a[i][j - 1];
        }
        for(int j = 0; j < x[i]; j++){
            int lo = l - (a[i][x[i]] - a[i][j]) + 1;
            int hi = a[i][j + 1];
            if(lo <= hi){
                add(lo, hi);
            }
        }
    }
    int ans = 0;
    for(auto p : st){
        ans += p.second - p.first + 1;
    }
    cout << ans;
}
signed main() {
    if(fopen(TN".inp", "r")){
        freopen(TN".inp", "r", stdin);
        freopen(TN".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test = 1;
    //cin >> test;
    while(test--){
        Solve();
    }
    return 0;
}

Compilation message (stderr)

lasers.cpp: In function 'int main()':
lasers.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(TN".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lasers.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen(TN".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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