Submission #987856

#	Time	Username	Problem	Language	Result	Execution time	Memory
987856		876pol	Street Lamps (APIO19_street_lamps)	C++17	60 / 100	5047 ms	29928 KiB

street_lamps

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using int128 = __int128_t;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define TRAV(e, a) for (const auto &e : a)
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl;

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
    out << "[";
    for (auto it = obj.begin(); it != obj.end(); it++) {
        out << &", "[2 * (it == obj.begin())] << *it;
    }
    return out << "]";
}

template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
    return out << "(" << obj.first << ", " << obj.second << ")";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    bool st2 = 1, st3 = 1;
    ll n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    string ts(s);
    vec<vec<ll>> queries(q, vec<ll>(3));
    FOR(i, 0, q) {
        string op;
        cin >> op;
        queries[i][0] = (op == "query");
        if (queries[i][0]) {
            cin >> queries[i][1] >> queries[i][2];
            st2 &= (queries[i][1] + 1 == queries[i][2]);
        } else {
            cin >> queries[i][1];
            st3 &= (ts[queries[i][1] - 1] == '0');
            ts[queries[i][1] - 1] = '1';
        }
    }
    if (st2) {
        vec<ll> illum(n + 1), hours(n + 1);
        CFOR(i, 1, n) illum[i] = (s[i - 1] == '1') ? 0 : -1;
        FOR(i, 0, q) {
            if (queries[i][0]) {
                if (illum[queries[i][1]] == -1) {
                    cout << hours[queries[i][1]] << "\n";
                } else {
                    cout << hours[queries[i][1]] + (i + 1) -
                                illum[queries[i][1]]
                         << "\n";
                }
            } else {
                if (illum[queries[i][1]] == -1) {
                    illum[queries[i][1]] = i + 1;
                } else {
                    hours[queries[i][1]] += (i + 1) - illum[queries[i][1]];
                    illum[queries[i][1]] = -1;
                }
            }
        }
    } else if (st3) {
#define lc(v) (v + 1)
#define rc(v) (v + 2 * (tm - tl + 1))
        vec<ll> seg(2 * n, 1e9);
        function<void(ll, ll, ll, ll, ll)> update = [&](ll v, ll tl, ll tr,
                                                        ll ind, ll x) {
            if (tl == tr && tl == ind) {
                seg[v] = x;
            } else {
                ll tm = (tl + tr) / 2;
                if (ind <= tm) {
                    update(lc(v), tl, tm, ind, x);
                } else {
                    update(rc(v), tm + 1, tr, ind, x);
                }
                seg[v] = max(seg[lc(v)], seg[rc(v)]);
            }
        };
        function<ll(ll, ll, ll, ll, ll)> query = [&](ll v, ll tl, ll tr, ll l,
                                                     ll r) -> ll {
            if (r < tl || tr < l) return 0;
            if (l <= tl && tr <= r) return seg[v];
            ll tm = (tl + tr) / 2;
            return max(query(lc(v), tl, tm, l, r),
                       query(rc(v), tm + 1, tr, l, r));
        };
        CFOR(i, 1, n) {
            if (s[i - 1] == '1') update(0, 1, n, i, 0);
        }
        FOR(i, 0, q) {
            if (queries[i][0]) {
                ll mx = query(0, 1, n, queries[i][1], queries[i][2] - 1);
                if (mx == 1e9) {
                    cout << "0\n";
                } else {
                    cout << (i + 1) - mx << "\n";
                }
            } else {
                update(0, 1, n, queries[i][1], i + 1);
            }
        }
    } else {
        FOR(i, 0, q) {
            if (queries[i][0]) {
                vec<ll> range(queries[i][2] - queries[i][1]);
                FOR(j, queries[i][1] - 1, queries[i][2] - 1) {
                    range[j - queries[i][1] + 1] = s[j] - '0';
                }
                ll cnt = accumulate(all(range), 0ll);
                ll ans = (cnt == range.size());
                FOR(j, 0, i) {
                    if (queries[j][0] == 0) {
                        ll ind = queries[j][1] - 1 - (queries[i][1] - 1);
                        if (ind < range.size()) {
                            cnt -= range[ind];
                            range[ind] ^= 1;
                            cnt += range[ind];
                        }
                    }
                    ans += (cnt == range.size());
                }
                cout << ans << "\n";
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:132:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |                 ll ans = (cnt == range.size());
      |                           ~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:136:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |                         if (ind < range.size()) {
      |                             ~~~~^~~~~~~~~~~~~~
street_lamps.cpp:142:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |                     ans += (cnt == range.size());
      |                             ~~~~^~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20