Submission #267578

#	Time	Username	Problem	Language	Result	Execution time	Memory
267578		blue	Street Lamps (APIO19_street_lamps)	C++11	20 / 100	1826 ms	35464 KiB

street_lamps

#include <iostream>
#include <vector>
using namespace std;

class segtree
{
public:
    int V = 300001;
    int L;
    int R;
    segtree* left = NULL;
    segtree* right = NULL;

    void update(int x, int u)
    {
        if(L == R) V = u;
        else
        {
            if(x <= (L+R)/2) left->update(x, u);
            else right->update(x, u);
            V = max(left->V, right->V);
        }
    }

    int query(int l, int r)
    {
        if(l <= L && R <= r) return V;
        if(r < L || R < l) return 0;
        return max(left->query(l, r), right->query(l, r));
    }

    segtree()
    {
        ;
    }

    segtree(int l, int r)
    {
        L = l;
        R = r;
        if(l == r) return;
        left = new segtree(l, (l+r)/2);
        right = new segtree((l+r)/2+1, r);
    }
};

int main()
{
    int n, q;
    cin >> n >> q;

    segtree T(1, n);

    string S;
    int a, b;
    cin >> S;
    for(int i = 1; i <= n; i++) if(S[i-1] == '1') T.update(i, 0);

    for(int i = 1; i <= q; i++)
    {
        cin >> S;
        if(S == "toggle")
        {
            cin >> a;
            T.update(a, i);
        }
        else
        {
            cin >> a >> b;
            cout << max(i - T.query(a, b-1), 0) << '\n';
        }
    }

}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20