Submission #1078256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078256		giaminh2211	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	210 ms	13652 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;
using ll=long long;

int n, q;
const int N=3e5+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 (stderr)

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
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20