oj.uz

Submission #987849

# Submission time Handle Problem Language Result Execution time Memory
987849 2024-05-23T16:41:56 Z 876pol Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 29708 KB 
#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;
    ll n, q;
    cin >> n >> q;
    string s;
    cin >> 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];
        }
    }
    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 {
        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

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:88: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]
   88 |                 ll ans = (cnt == range.size());
      |                           ~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:92: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]
   92 |                         if (ind < range.size()) {
      |                             ~~~~^~~~~~~~~~~~~~
street_lamps.cpp:98: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]
   98 |                     ans += (cnt == range.size());
      |                             ~~~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 17744 KB Output is correct
2 Correct 69 ms 21328 KB Output is correct
3 Correct 71 ms 21844 KB Output is correct
4 Correct 83 ms 27620 KB Output is correct
5 Correct 84 ms 28132 KB Output is correct
6 Correct 91 ms 27404 KB Output is correct
7 Correct 90 ms 28192 KB Output is correct
8 Correct 95 ms 29708 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 532 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2619 ms 21416 KB Output is correct
6 Execution timed out 5016 ms 21248 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Execution timed out 5066 ms 21648 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 65 ms 17744 KB Output is correct
9 Correct 69 ms 21328 KB Output is correct
10 Correct 71 ms 21844 KB Output is correct
11 Correct 83 ms 27620 KB Output is correct
12 Correct 84 ms 28132 KB Output is correct
13 Correct 91 ms 27404 KB Output is correct
14 Correct 90 ms 28192 KB Output is correct
15 Correct 95 ms 29708 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 2 ms 532 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Correct 2 ms 344 KB Output is correct
20 Correct 2619 ms 21416 KB Output is correct
21 Execution timed out 5016 ms 21248 KB Time limit exceeded
22 Halted 0 ms 0 KB -