oj.uz

Submission #211449

# Submission time Handle Problem Language Result Execution time Memory
211449 2020-03-20T11:16:41 Z VEGAnn Street Lamps (APIO19_street_lamps) C++14
20 / 100
 252 ms 16524 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define pll pair<ll, ll>
#define MP make_pair
#define PB push_back
#define pii pair<int, int>
#define pi3 pair<pii, int>
#define ft first
#define sd second
#define MP3(a,b,c) MP(MP(a,b),c)
using namespace std;
typedef long long ll;
const int N = 300100;
const int Q = 300100;
const int oo = 2e9;
const int B = 1;
string s, qr;
int n, q, mn[N], l[N], r[N], st[4 * N];
bool typ[N];

void build(int v, int l, int r){
    if (l == r) {
        st[v] = mn[l];
        return;
    }
    int md = (l + r) >> 1;
    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    st[v] = max(st[v + v], st[v + v + 1]);
}

int get(int v, int tl, int tr, int l, int r){
    if (l > r) return -q;

    if (tl == l && tr == r) return st[v];

    int md = (tl + tr) >> 1;

    return max(get(v + v, tl, md, l, min(r, md)),
               get(v + v + 1, md + 1, tr, max(md + 1, l), r));
}

int main(){

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#else
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif // _LOCAL

    cin >> n >> q >> s;

    for (int i = 0; i < n; i++){
        mn[i] = (s[i] == '1' ? -1 : q);
    }

    for (int i = 0; i < q; i++){
        string qr; cin >> qr;
        if (qr[0] == 't'){
            typ[i] = 1;
            int x; cin >> x;
            x--;

            mn[x] = i;
        } else {
            cin >> l[i] >> r[i];
            l[i]--;
            r[i] -= 2;
        }
    }

    build(1, 0, n - 1);

    for (int i = 0; i < q; i++)
        if (!typ[i])
            cout << max(0, i - get(1, 0, n - 1, l[i], r[i])) << '\n';

    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 79 ms 3704 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 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 67 ms 9100 KB Output is correct
6 Correct 120 ms 12556 KB Output is correct
7 Correct 186 ms 14348 KB Output is correct
8 Correct 242 ms 16300 KB Output is correct
9 Correct 96 ms 6136 KB Output is correct
10 Correct 104 ms 6600 KB Output is correct
11 Correct 108 ms 6776 KB Output is correct
12 Correct 231 ms 14984 KB Output is correct
13 Correct 252 ms 16524 KB Output is correct

Subtask #4
0 / 20.0

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