oj.uz

Submission #1005015

# Submission time Handle Problem Language Result Execution time Memory
1005015 2024-06-22T06:12:44 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 441 ms 5144 KB 
#include <bits/stdc++.h>
using namespace std;

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


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;
    }

    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;
        cin >> qx;

        if (qx[0] == 't'){
            int x;
            cin >> x;
            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, b;
            cin >> a >> b;
            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++;
    }
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 1348 KB Output is correct
2 Correct 241 ms 1360 KB Output is correct
3 Correct 242 ms 1620 KB Output is correct
4 Correct 275 ms 4848 KB Output is correct
5 Correct 291 ms 4076 KB Output is correct
6 Correct 255 ms 4848 KB Output is correct
7 Correct 435 ms 1264 KB Output is correct
8 Correct 441 ms 5144 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 245 ms 1348 KB Output is correct
9 Correct 241 ms 1360 KB Output is correct
10 Correct 242 ms 1620 KB Output is correct
11 Correct 275 ms 4848 KB Output is correct
12 Correct 291 ms 4076 KB Output is correct
13 Correct 255 ms 4848 KB Output is correct
14 Correct 435 ms 1264 KB Output is correct
15 Correct 441 ms 5144 KB Output is correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -