Submission #1005137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005137		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	416 ms	25000 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 10;
int n, q, store[N], at[N], seg[4 * N];
string s;
pair<int, int> last[N];

void modify(int p, int x, int v = 1, int s = 0, int e = n){
    if (e - s == 1){
        seg[v] = x;
        return;
    }

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;

    if (p < mid) modify(p, x, lc, s, mid);
    else modify(p, x, rc, mid, e);

    seg[v] = max(seg[lc], seg[rc]);
}

int get(int l, int r, int v = 1, int s = 0, int e = n){
    if (r <= s || e <= l) return 0;
    if (l <= s && e <= r) return seg[v];

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;

    return max(get(l, r, lc, s, mid), get(l, r, rc, mid, e));
}

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

    // if (n <= 100 and q <= 100){
    //     vector<string> vec;
    //     vec.push_back(s);
    //     for (int i = 0; i < q; i ++){
    //         string qx;
    //         cin >> qx;

    //         if (qx[0] == 't'){
    //             int x;
    //             cin >> x;
    //             x--;
    //             s[x] = '1' - s[x] + '0';
    //         }
    //         else{
    //             int a, b;
    //             cin >> a >> b;
    //             a--, b--;

    //             int ans = 0;
    //             for (string x : vec){
    //                 bool good = 1;
    //                 for (int i = a; i < b; i ++)
    //                     if (x[i] == '0')
    //                         good = 0;
    //                 ans += good;
    //             }

    //             cout << ans << endl;
    //         }
    //         vec.push_back(s);    
    //     }
    //     return 0;
    // }

    bool subtask2 = 1;
    vector<pair<string, pair<int, int>>> query;
    for (int i = 0; i < q; i ++){
        string qx;
        int x, y;
        cin >> qx >> x;
        if (qx[0] == 'q')
            cin >> y; 
        query.push_back({qx, {x, y}});

        if (qx[0] == 'q' and (y - x) > 1)
            subtask2 = 0;
    }

    if (subtask2){
        for (int i = 0; i < n; i ++)
            if (s[i] == '1')
                last[i] = {0, -1};

        int tme = 0;
        for (int i = 0; i < q; i ++){
            string qx = query[i].first;

            if (qx[0] == 't'){
                int x;
                x = query[i].second.first;
                x--;
                
                if (s[x] == '1'){
                    last[x].second = tme;
                    s[x] = '0';
                    store[x] += last[x].second - last[x].first + 1;
                }
                else{
                    last[x] = {tme + 1, -1};
                    s[x] = '1';
                }
            }
            else{
                int a = query[i].second.first, b = query[i].second.second;
                a--, b--;

                int val = 0;
                if (last[a].second == -1 and last[a].first != -1)
                    val = tme - last[a].first + 1;

                // cout << a << " : " << last[a].first << " " << last[a].second << ", cur time = " << tme << endl;

                cout << store[a] + val << endl;
            }
            tme++;
        }
        return 0;
    }

    cout << "HERE" << endl;

    for (int i = 0; i < n; i ++){
        if (s[i] == '0')
            at[i] = n + q + 10;
        else
            at[i] = 0;

        modify(i, at[i]);
    }

    int tme = 0;
    for (int i = 0; i < q; i ++){
        string qx = query[i].first;

        if (qx[0] == 't'){
            int x = query[i].second.first;
            x--;
            at[x] = tme + 1;
            modify(x, at[x]);
        }
        else{
            int a = query[i].second.first;
            int b = query[i].second.second;
            a--, b--;

            int mx = get(a, b);
            cout << max(0, tme - mx + 1) << endl;
        }
        tme++;
    }
}

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