Submission #211449

#	Time	Username	Problem	Language	Result	Execution time	Memory
211449		VEGAnn	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	252 ms	16524 KiB

street_lamps

#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
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20