oj.uz

Submission #1078252

# Submission time Handle Problem Language Result Execution time Memory
1078252 2024-08-27T14:33:33 Z giaminh2211 Street Lamps (APIO19_street_lamps) C++14
0 / 100
 64 ms 6560 KB 
#include <bits/stdc++.h>

using namespace std;
using ll=long long;

int n, q;
const int N=2e5+13;
int st[N << 2];
char c;
int a[N];
string type;
int x, y;

void update(int id, int l, int r, int i, int val){
    if(l > i || r < i) return;
    if(l==r){
        st[id]=val;
        return;
    }
    int mid=l+r >> 1;
    update(id << 1, l, mid, i, val);
    update(id << 1 | 1, mid+1, r, i, val);
    st[id] = max(st[id << 1], st[id << 1 | 1]);
}

int get(int id, int l, int r, int u, int v){
    if(l > v || r < u) return -1e9;
    if(u<=l && r<=v){
        return st[id];
    }
    int mid=l+r>>1;
    int get1=get(id << 1, l, mid, u, v);
    int get2=get(id << 1 | 1, mid+1, r, u, v);
    return max(get1, get2);
}

void scan(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> c;
        a[i]=c-'0';
        if(a[i]==1) update(1, 1, n, i, 0);
        else update(1, 1, n, i, 1e9);
    }
}

void solve(){
    for(int t=1; t<=q; t++){
        cin >> type >> x;
        if(type=="toggle"){
            a[x] ^= 1;
            update(1, 1, n, x, a[x]);
            if(a[x]==1) update(1, 1, n, x, t);
            else update(1, 1, n, x, 1e9);
        }
        else{
            cin >> y;
            y--;
            int val=get(1, 1, n, x, y);
            if(val <= 1e8) cout << t-val;
            else cout << 0;
            cout << '\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

Compilation message

street_lamps.cpp: In function 'void update(int, int, int, int, int)':
street_lamps.cpp:20:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |     int mid=l+r >> 1;
      |             ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, int)':
street_lamps.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
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 #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Runtime error 24 ms 6560 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
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 -