oj.uz

Submission #716549

# Submission time Handle Problem Language Result Execution time Memory
716549 2023-03-30T09:43:56 Z 1zaid1 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 306 ms 32192 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'

const signed M = 3e6, MOD = 998244353;

int N = 1 << 20;
int seg[M];

void update(int ind) {
    while (ind /= 2) seg[ind] = max(seg[ind*2], seg[ind*2+1]);
}
 
int query(int L, int R, int l = 1, int r = N, int ind = 1) {
    if (r < L || l > R) return 0;
    if (L <= l && r <= R) return seg[ind];
    return max(query(L, R, l, (l+r)/2, ind*2), query(L, R, (l+r)/2+1, r, ind*2+1));
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    for (int &i:seg) i = INT_MAX;

    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') seg[N+i] = 0, update(N+i);
    }

    for (int i = 1; i <= q; i++) {
        string s;
        cin >> s;

        if (s == "query") {
            int l, r;
            cin >> l >> r;
            cout << max(0ll, i-query(l, r-1)) << endl;
        } else {
            int x;
            cin >> x;
            seg[N+x-1] = i;
            update(N+x-1);
        }
    }

    return 0;
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 24268 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 11 ms 23776 KB Output is correct
2 Correct 11 ms 23684 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 13 ms 23748 KB Output is correct
5 Correct 106 ms 28424 KB Output is correct
6 Correct 166 ms 29068 KB Output is correct
7 Correct 197 ms 29852 KB Output is correct
8 Correct 248 ms 32192 KB Output is correct
9 Correct 143 ms 27408 KB Output is correct
10 Correct 126 ms 27652 KB Output is correct
11 Correct 122 ms 27880 KB Output is correct
12 Correct 306 ms 30680 KB Output is correct
13 Correct 278 ms 32064 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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