Submission #528189

#	Time	Username	Problem	Language	Result	Execution time	Memory
528189		Olympia	가로등 (APIO19_street_lamps)	C++17	20 / 100	1956 ms	18912 KiB

street_lamps

#include <cmath>
#include <cassert>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
#include <stack>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("Ofast")
using namespace std;
struct Node {
    int sum;
    int lastOkay;
};
struct segmentTree {
    vector<int> v;
    vector<Node> val;

    Node id = {0, 0};

    Node merge (Node a, Node b) {
        return {a.sum + b.sum, max(a.lastOkay, b.lastOkay)};
    }

    Node query(int dum, int tl, int tr, int& l, int& r) {
        if (tr < l || tl > r) {
            return id;
        }
        if (tl >= l && tr <= r) {
            return val[dum];
        }
        int mid = (tl + tr) >> 1;
        dum = dum << 1;
        return merge(query(dum, tl, mid, l, r), query(dum + 1, mid + 1, tr, l, r));
    }

    Node query(int l, int r) {
        return query(1, 0, (int)v.size() - 1, l, r);
    }

    void update (int x, Node y) {
        int cur = (int) v.size() + x;
        int curX = x;
        int curY = x;
        while (true) {
            val[cur] = merge(merge(query(curX, x - 1), query(x + 1, curY)), y);
            //cout << val[cur].lastOkay << '\n';
            if (cur == 0) {
                break;
            }
            if(cur % 2 == 0) {
                curY = 2 * curY - curX + 1;
            } else {
                curX = 2 * curX - curY - 1;
            }
            cur /= 2;
        }
    }

    void update (int x, int y, int now) {
        Node myNode;
        if (y == 0) {
            myNode.lastOkay = query(x, x).lastOkay;
            myNode.sum = 0;
        } else {
            myNode.lastOkay = now;
            myNode.sum = 1;
        }
        update(x, myNode);
    }

    void resz(int n) {
        v.resize((1 << (int) ceil(log2(n))));
        val.resize(v.size() * 2);
    }

};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    segmentTree st;
    int N, Q;
    cin >> N >> Q;
    st.resz(N);
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '1') {
            st.update(i, 1, 0);
        }
    }
    for (int i = 1; i <= Q; i++) {
        string str;
        cin >> str;
        if (str == "query") {
            int l, r; cin >> l >> r; l--, r -= 2;
            if (st.query(l, r).sum != r - l + 1) {
                cout << 0 << '\n';
                continue;
            }
            cout << i - st.query(l, r).lastOkay << '\n';
        } else {
            int x; cin >> x; x--;
            if (st.query(x, x).sum == 0) {
                st.update(x, 1, i);
            } else {
                st.update(x, 0, i);
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   16 | #pragma GCC optimization ("O3")
      | 
street_lamps.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   17 | #pragma GCC optimization ("unroll-loops")
      | 
street_lamps.cpp:18: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   18 | #pragma GCC optimization ("Ofast")
      | 
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     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