oj.uz

Submission #257670

# Submission time Handle Problem Language Result Execution time Memory
257670 2020-08-04T14:19:02 Z trttrttrt Street Lamps (APIO19_street_lamps) C++17
20 / 100
 308 ms 8280 KB 
// Dmitry _kun_ Sayutin (2019)

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;
using std::swap;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    return res;
}



#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

// RMaxQ
vector<int> tree;
void build(int v, int l, int r, vector<int>& arr) {
    if (l == r - 1) {
        tree[v] = arr[l];
        return;
    }

    int m = l + (r - l) / 2;
    build(2 * v + 1, l, m, arr);
    build(2 * v + 2, m, r, arr);

    tree[v] = max(tree[2 * v + 1], tree[2 * v + 2]);
}

int get_max(int v, int vl, int vr, int l, int r) {
    if (vr <= l or r <= vl)
        return TYPEMIN(int);

    if (l <= vl and vr <= r)
        return tree[v];

    int m = vl + (vr - vl) / 2;
    return max(get_max(2 * v + 1, vl, m, l, r),
               get_max(2 * v + 2, m, vr, l, r));
}

void change(int v, int vl, int vr, int i, int val) {
    if (vl == vr - 1) {
        tree[v] = val;
        return;
    }

    int m = vl + (vr - vl) / 2;
    if (i < m)
        change(2 * v + 1, vl, m, i, val);
    else
        change(2 * v + 2, m, vr, i, val);

    tree[v] = max(tree[2 * v + 1], tree[2 * v + 2]);
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // code here
    int n = input<int>();
    int q = input<int>();

    vector<int> arr(n);
    for (int i = 0; i != n; ++i)
        if (input<char>() == '1')
            arr[i] = 0;
        else
            arr[i] = TYPEMAX(int);

    tree.resize(4 * n);
    build(0, 0, n, arr);

    for (int i = 1; i <= q; ++i) {
        if (input<string>() == "toggle") {
            int pos = input<int>() - 1;
            arr[pos] = i;

            change(0, 0, n, pos, i);
        } else {
            int a = input<int>() - 1;
            int b = input<int>() - 1;

            int tm = get_max(0, 0, n, a, b);

            int ans = 0;
            if (tm != TYPEMAX(int))
                ans = i - tm;

            cout << ans << "\n";
        }
    }

    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 1248 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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 152 ms 6260 KB Output is correct
6 Correct 204 ms 6396 KB Output is correct
7 Correct 262 ms 6648 KB Output is correct
8 Correct 294 ms 8280 KB Output is correct
9 Correct 106 ms 1272 KB Output is correct
10 Correct 108 ms 1272 KB Output is correct
11 Correct 118 ms 1416 KB Output is correct
12 Correct 261 ms 6904 KB Output is correct
13 Correct 308 ms 8184 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 1 ms 384 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 384 KB Output isn't correct
2 Halted 0 ms 0 KB -