Submission #328351

#	Time	Username	Problem	Language	Result	Execution time	Memory
328351		ryangohca	Lasers (NOI19_lasers)	C++17	100 / 100	142 ms	8580 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
set<pair<int, int>> nums;
void set_range(int a, int b){
    auto itr = nums.lower_bound({a, 0});
    int l = a, r = b;
    if (itr != nums.begin()){
        --itr;
        int a1, b1; tie(a1, b1) = *itr;
        itr++;
        if (b1 >= a){
            nums.erase({a1, b1});
            l = a1;
        }
        if (b1 >= b){
            r = b1;
        }
    }
    while (itr != nums.end()){
        int a1, b1; tie(a1, b1) = *itr;
        if (b1 > b) break;
        itr++;
        nums.erase({a1, b1});
    }
    if (itr != nums.end()){
        int a1, b1; tie(a1, b1) = *itr;
        if (a1 <= b){
            nums.erase(itr);
            r = b1;
        }
    }
    nums.insert({l, r});
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int l, r; cin >> l >> r;
    for (int j = 0; j < r; j++){
        vector<pii> ranges;
        vector<int> walls;
        int rptr = l;
        int lptr = 0;
        int x; cin >> x;
        for (int i = 0; i < x; i++){
            int g; cin >> g;
            rptr -= g;
            walls.push_back(g);
        }
        if (rptr == 0){
            cout << l << '\n';
            return 0;
        }
        ranges.push_back({lptr + 1, rptr});
        for (int i = 0; i < x; i++){
            lptr += walls[i];
            rptr += walls[i];
            if (ranges.back().second >= lptr){
                auto [l1, r1] = ranges.back();
                ranges.pop_back();
                ranges.push_back({l1, rptr});
            } else {
                ranges.push_back({lptr + 1, rptr});
            }
        }
        int lfree = ranges[0].second + 1;
        for (int i = 1; i < ranges.size(); i++){
            if (lfree <= ranges[i].first - 1) set_range(lfree, ranges[i].first - 1);
            lfree = ranges[i].second + 1;
        }
    }
    int ans = 0;
    for (auto [a, b] : nums){
        ans += b - a + 1;
    }
    cout << ans << '\n';
}

Compilation message (stderr)

lasers.cpp: In function 'int main()':
lasers.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int i = 1; i < ranges.size(); i++){
      |                         ~~^~~~~~~~~~~~~~~

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