oj.uz

Submission #267578

# Submission time Handle Problem Language Result Execution time Memory
267578 2020-08-16T04:55:03 Z blue Street Lamps (APIO19_street_lamps) C++11
20 / 100
 1826 ms 35464 KB 
#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.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 695 ms 892 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 2 ms 416 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 616 ms 32692 KB Output is correct
6 Correct 990 ms 33432 KB Output is correct
7 Correct 1457 ms 33556 KB Output is correct
8 Correct 1826 ms 35440 KB Output is correct
9 Correct 867 ms 4216 KB Output is correct
10 Correct 948 ms 4636 KB Output is correct
11 Correct 975 ms 4612 KB Output is correct
12 Correct 1753 ms 33948 KB Output is correct
13 Correct 1775 ms 35464 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 4 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 256 KB Output isn't correct
2 Halted 0 ms 0 KB -