oj.uz

답안 #267578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
267578 2020-08-16T04:55:03 Z blue 가로등 (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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 695 ms 892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -