oj.uz

Submission #983236

# Submission time Handle Problem Language Result Execution time Memory
983236 2024-05-15T09:40:23 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 213 ms 23888 KB 
#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>

using namespace std;

int tt = 1, n;
string s;
int k[1001][1001];
int last[300005], kol[300005], l[300005], r[300005];
string type[300005];
int mx[4 * 300005];
void up(int l, int r, int ind, int num, int v){
    if(l > ind || r < ind) return;
    if(l == r){
        mx[v] = num;
        return;
    }
    int mid = (l + r) / 2;
    up(l, mid, ind, num, v * 2);
    up(mid + 1, r, ind, num, v * 2 + 1);
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}
int get_mx(int l, int r, int l1, int r1, int v){
    if(l > r1 || l1 > r) return 0;
    if(l >= l1 && r1 >= r) return mx[v];
    int mid = (l + r) / 2;
    return max(get_mx(l, mid, l1, r1, v * 2), get_mx(mid + 1, r, l1, r1, v * 2 + 1));
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> tt;
    cin >> s;
    // if(n <= 100 && tt <= 100){
    //     while(tt--){
    //         string ss;
    //         cin >> ss;
    //         for(int i = 1; i <= n; i++){
    //             for(int j = i + 1; j <= n + 1; j++){
    //                 if(s[j - 2] == '1') k[i][j]++;
    //                 else break;
    //             }
    //         }
    //         if(ss[0] == 'q'){
    //             int a, b;
    //             cin >> a >> b;
    //             cout << k[a][b] << "\n";
    //         }
    //         else{
    //             int p;
    //             cin >> p;
    //             if(s[p - 1] == '0') s[p - 1] = '1';
    //             else s[p - 1] = '0';

    //         }
    //     }
    //     return 0;
    // }
    bool f = 0;
    for(int i = 1; i <= tt; i++){
        cin >> type[i] >> l[i];
        if(type[i][0] == 'q') cin >> r[i];
        if(type[i][0] == 'q' && r[i] - 1 != l[i]) f = 1;
    }
    // if(!f){
    //     for(int i = 1; i <= tt; i++){
    //         if(type[i][0] == 'q'){
    //             int num = kol[l[i]];
    //             if(s[l[i] - 1] == '1') num += (i - last[l[i]]);
    //             cout << num << "\n";
    //         }
    //         else{
    //             if(s[l[i] - 1] == '1'){
    //                 kol[l[i]] += (i - last[l[i]]);
    //                 last[l[i]] = i;
    //                 s[l[i] - 1] = '0';
    //             }
    //             else{
    //                 last[l[i]] = i;
    //                 s[l[i] - 1] = '1';
    //             }
    //         }
    //     }
    //     return 0;
    // }
    for(int i = 0; i < n; i++){
        if(s[i] == '0') up(1, n, i + 1, 1e9, 1);
    }
    for(int i = 1; i <= tt; i++){
        if(type[i][0] == 'q'){
            cout << max(0, i - get_mx(1, n, l[i], r[i] - 1, 1)) << "\n";
        }
        else{
            up(1, n, l[i], i, 1);
        }
    }
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:84:10: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   84 |     bool f = 0;
      |          ^

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12724 KB Output is correct
4 Correct 3 ms 12736 KB Output is correct
5 Correct 140 ms 21624 KB Output is correct
6 Correct 157 ms 22756 KB Output is correct
7 Correct 157 ms 23012 KB Output is correct
8 Correct 164 ms 21108 KB Output is correct
9 Correct 63 ms 16212 KB Output is correct
10 Correct 68 ms 16596 KB Output is correct
11 Correct 70 ms 16828 KB Output is correct
12 Correct 213 ms 23888 KB Output is correct
13 Correct 163 ms 21040 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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