Submission #1027544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027544		caterpillow	Lasers (NOI19_lasers)	C++17	100 / 100	252 ms	29068 KiB

lasers

#include <bits/stdc++.h>

using namespace std;

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<typename Tuple, size_t... Is>
void print_tuple(const Tuple& t, index_sequence<Is...>) {
    ((cerr << (Is == 0 ? "{" : ", ") << get<Is>(t)), ...);
    cerr << "}";
}

template<typename... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
    print_tuple(t, index_sequence_for<Args...>{});
    return os;
}

ostream& operator<<(ostream& os, string& s) {
    for (char c : s) os << c; 
    return os;
}

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

template<typename T, typename V>
ostream& operator<<(ostream& os, const pair<T, V> p) {
    os << "{" << p.f << ", " << p.s << "}";
    return os;
}

template <typename T, typename... V>
void printer(const char *names, T &&head, V &&...tail) {
    int i = 0;
    while (names[i] != '\0' && names[i] != ',') i++;
    constexpr bool is_str = is_same_v<decay_t<T>, const char*>;
    if constexpr (is_str) cerr << head; // ignore directly passed strings
    else cerr.write(names, i) << " = " << head; 
    if constexpr (sizeof...(tail)) cerr << (is_str ? "" : ","), printer(names + i + 1, tail...);
    else cerr << endl;
}

#ifdef LOCAL
#define dbg(...) std::cerr << __LINE__ << ": ", printer(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

instead, we want to count the # of lasers which are possible to not be blocked

for each laser, we just need to know if we can construct a configuration
where its not blocked

u can do the greedy strategy, where you pretend to slide each piece in each row to the left as much as possible,
and then sliding the rest to the right, and hoping u dont get blocked in the middle

this means we can just try each number of blocks aligned to the left on each row, and then range increment
the "gap" in the center, indicating that there is a configuration of the row such that light passes through
then, we just need to check which lights have a non-zero value over all rows

merge ranges, insert as events, then sweep

*/

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int cs, rs; cin >> cs >> rs;
    map<int, int> evs;
    evs[cs] = 0;
    F0R (_, rs) {
        int n; cin >> n;
        vt<int> blox(n + 1);
        F0R (i, n) cin >> blox[i + 1];
        FOR (i, 1, n + 1) blox[i] += blox[i - 1];
        int tot = accumulate(all(blox), 0);
        int l = 0, r = 0; // inc exc
        F0R (i, n + 1) {
            int lhs = blox[i], rhs = blox.back() - blox[i];
            int nl = lhs, nr = cs - rhs;
            if (nl <= r) { // merge ranges
                r = nr;
            } else { // flush range to events
                evs[l]++;
                evs[r]--;
                tie(l, r) = pi {nl, nr};
            }
        }
        evs[l]++;
        evs[r]--;
    }

    int ans = 0, last = 0, pfx = 0;
    for (auto [c, diff] : evs) { // exc
        if (pfx != rs) ans += c - last;
        pfx += diff;
        last = c;
    }
    cout << ans << endl;
}

Compilation message (stderr)

lasers.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 | main() {
      | ^~~~
lasers.cpp: In function 'int main()':
lasers.cpp:101:13: warning: unused variable 'tot' [-Wunused-variable]
  101 |         int tot = accumulate(all(blox), 0);
      |             ^~~

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