oj.uz

Submission #987838

# Submission time Handle Problem Language Result Execution time Memory
987838 2024-05-23T16:35:30 Z 876pol Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 27344 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);
    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];
        } else {
            cin >> queries[i][1];
        }
    }
    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:64:27: 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]
   64 |             ll ans = (cnt == range.size());
      |                       ~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:68:29: 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]
   68 |                     if (ind < range.size()) {
      |                         ~~~~^~~~~~~~~~~~~~
street_lamps.cpp:74:29: 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]
   74 |                 ans += (cnt == range.size());
      |                         ~~~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 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 344 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5075 ms 20252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2502 ms 25784 KB Output is correct
6 Execution timed out 5036 ms 25912 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 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Execution timed out 5048 ms 27344 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 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 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 344 KB Output is correct
8 Execution timed out 5075 ms 20252 KB Time limit exceeded
9 Halted 0 ms 0 KB -