oj.uz

Submission #528189

# Submission time Handle Problem Language Result Execution time Memory
528189 2022-02-19T16:19:31 Z Olympia Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1956 ms 18912 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 229 ms 3948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 324 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 4 ms 324 KB Output is correct
4 Correct 4 ms 332 KB Output is correct
5 Correct 1956 ms 15216 KB Output is correct
6 Correct 1794 ms 15876 KB Output is correct
7 Correct 1674 ms 16608 KB Output is correct
8 Correct 1667 ms 18852 KB Output is correct
9 Correct 89 ms 3900 KB Output is correct
10 Correct 90 ms 4216 KB Output is correct
11 Correct 107 ms 4540 KB Output is correct
12 Correct 201 ms 17464 KB Output is correct
13 Correct 1558 ms 18912 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Incorrect 2 ms 324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -