oj.uz

답안 #721779

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721779 2023-04-11T07:14:15 Z GrandTiger1729 가로등 (APIO19_street_lamps) C++17
20 / 100
 503 ms 31044 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
struct SegTree {
    int l, r, mid;
    int val = INF;
    SegTree *lc, *rc;
    SegTree(int _l, int _r): l(_l), r(_r){
        mid = (l + r) / 2;
        if (l == r - 1) return;
        lc = new SegTree(l, mid);
        rc = new SegTree(mid, r);
    }
    void pull(){
        val = max(lc->val, rc->val);
    }
    void update(int i, int u){
        if (l == r - 1)
            return void(val = u);
        if (i < mid)
            lc->update(i, u);
        else
            rc->update(i, u);
        pull();
    }
    int query(int ll, int rr){
        if (ll <= l && rr >= r)
            return val;
        int ret = -INF;
        if (ll < mid)
            ret = max(ret, lc->query(ll, rr));
        if (mid < rr)
            ret = max(ret, rc->query(ll, rr));
        return ret;
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    vector<bool> a(n);
    for (int i = 0; i < n; i++){
        char c; cin >> c;
        a[i] = c - '0';
    }
    SegTree st(0, n);
    for (int i = 0; i < n; i++)
        if (a[i])
            st.update(i, 0);
    for (int qq = 1; qq <= q; qq++){
        string ty; cin >> ty;
        if (ty == "toggle"){
            int i; cin >> i;
            i--;
            st.update(i, qq);
        }else{
            int l, r; cin >> l >> r;
            l--, r--;
            cout << max(0, qq - st.query(l, r)) << '\n';
        }
    }
    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 307 ms 29264 KB Output is correct
6 Correct 317 ms 29260 KB Output is correct
7 Correct 444 ms 29308 KB Output is correct
8 Correct 463 ms 31044 KB Output is correct
9 Correct 77 ms 1612 KB Output is correct
10 Correct 90 ms 1684 KB Output is correct
11 Correct 92 ms 1772 KB Output is correct
12 Correct 442 ms 29676 KB Output is correct
13 Correct 503 ms 30916 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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