Submission #538317

#	Time	Username	Problem	Language	Result	Execution time	Memory
538317		Olympia	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	369 ms	12812 KiB

street_lamps

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <limits.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;
const int MOD = 1e9;

template<class T>
class SegmentTreeMax {
public:
    vector<T> val;
    SegmentTreeMax (int N) {
        N = (1 << ((int)floor(log2(N - 1)) + 1));
        this->N = N;
        val.assign(2 * N, ID);
    }

    void update (int x, T y) {
        x += N - 1;
        val[x] = y;
        while (x != 0) {
            x = (x - 1)/2;
            val[x] = merge(val[2 * x + 1], val[2 * x + 2]);
        }
    }

    T query (int ind, const int l, const int r, int tl, int tr) {
        if (tl >= l && tr <= r) {
            return val[ind];
        }
        if (tr < l || tl > r) {
            return ID;
        }
        return merge(query(2 * ind + 1, l, r, tl, (tl + tr)/2), query(2 * ind + 2, l, r, (tl + tr)/2 + 1, tr));
    }

    T query (int l, int r) {
        return query(0, l, r, 0, N - 1);
    }
private:
    T ID = 0;
    T merge (T x, T y) {
        return max(x, y);
    }
    int N;
};

template<class T>
class SegmentTreeAnd {
public:
    vector<T> val;
    SegmentTreeAnd (int N) {
        N = (1 << ((int)floor(log2(N - 1)) + 1));
        this->N = N;
        val.assign(2 * N, ID);
    }

    void update (int x, T y) {
        x += N - 1;
        val[x] = y;
        while (x != 0) {
            x = (x - 1)/2;
            val[x] = merge(val[2 * x + 1], val[2 * x + 2]);
        }
    }

    T query (int ind, const int l, const int r, int tl, int tr) {
        if (tl >= l && tr <= r) {
            return val[ind];
        }
        if (tr < l || tl > r) {
            return ID;
        }
        return merge(query(2 * ind + 1, l, r, tl, (tl + tr)/2), query(2 * ind + 2, l, r, (tl + tr)/2 + 1, tr));
    }

    T query (int l, int r) {
        return query(0, l, r, 0, N - 1);
    }
private:
    T ID = 1;
    T merge (T x, T y) {
        return x & y;
    }
    int N;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, Q;
    cin >> N >> Q;
    string s;
    cin >> s;
    SegmentTreeAnd<bool> sta(N);
    SegmentTreeMax<int> stm(N);
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '0') {
            sta.update(i, false);
        } else {
            sta.update(i, true);
        }
        stm.update(i, 0);
    }
    for (int q = 1; q <= Q; q++) {
        string str;
        cin >> str;
        if (str == "query") {
            int x, y; cin >> x >> y; x--, y--;
            if (sta.query(x, y - 1) == 0) {
                cout << 0 << '\n';
                continue;
            }
            cout << q- stm.query(x, y - 1) << '\n';
        } else {
            int x; cin >> x; x--;
            stm.update(x, q);
            if (sta.query(x,x) == 0) {
                sta.update(x, true);
            } else {
                sta.update(x, false);
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp:14: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   14 | #pragma GCC optimization ("O3")
      | 
street_lamps.cpp:15: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   15 | #pragma GCC optimization ("unroll-loops")
      | 
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i = 0; i < s.length(); i++) {
      |                     ~~^~~~~~~~~~~~

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