oj.uz

Submission #1005138

# Submission time Handle Problem Language Result Execution time Memory
1005138 2024-06-22T07:48:26 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
60 / 100
 554 ms 30036 KB 
#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;
    }

    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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2488 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 24240 KB Output is correct
2 Correct 259 ms 23156 KB Output is correct
3 Correct 254 ms 24512 KB Output is correct
4 Correct 268 ms 24844 KB Output is correct
5 Correct 297 ms 23808 KB Output is correct
6 Correct 259 ms 24080 KB Output is correct
7 Correct 422 ms 25100 KB Output is correct
8 Correct 445 ms 24264 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 175 ms 24220 KB Output is correct
6 Correct 289 ms 28728 KB Output is correct
7 Correct 394 ms 29628 KB Output is correct
8 Correct 538 ms 30036 KB Output is correct
9 Correct 319 ms 17584 KB Output is correct
10 Correct 361 ms 27364 KB Output is correct
11 Correct 353 ms 28336 KB Output is correct
12 Correct 512 ms 29460 KB Output is correct
13 Correct 554 ms 29748 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2488 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 245 ms 24240 KB Output is correct
9 Correct 259 ms 23156 KB Output is correct
10 Correct 254 ms 24512 KB Output is correct
11 Correct 268 ms 24844 KB Output is correct
12 Correct 297 ms 23808 KB Output is correct
13 Correct 259 ms 24080 KB Output is correct
14 Correct 422 ms 25100 KB Output is correct
15 Correct 445 ms 24264 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4444 KB Output is correct
19 Correct 2 ms 4444 KB Output is correct
20 Correct 175 ms 24220 KB Output is correct
21 Correct 289 ms 28728 KB Output is correct
22 Correct 394 ms 29628 KB Output is correct
23 Correct 538 ms 30036 KB Output is correct
24 Correct 319 ms 17584 KB Output is correct
25 Correct 361 ms 27364 KB Output is correct
26 Correct 353 ms 28336 KB Output is correct
27 Correct 512 ms 29460 KB Output is correct
28 Correct 554 ms 29748 KB Output is correct
29 Correct 2 ms 4444 KB Output is correct
30 Incorrect 2 ms 4444 KB Output isn't correct
31 Halted 0 ms 0 KB -