Submission #494268

#	Time	Username	Problem	Language	Result	Execution time	Memory
494268		teee	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	80 ms	4420 KiB

street_lamps

#include <iostream>
using namespace std;
const int inf=300'010;
struct node{
    int smax,emin;
} tree[inf*4];
string v;
int now;
node merge(node a,node b){
    return {max(a.smax,b.smax),min(a.emin,b.emin)};
}
node init(int n,int s,int e){
    if(s==e) {
        if(v[s-1]=='0')
            tree[n]={-1,0};
        else tree[n]={0,inf};
        return tree[n];
    }
    int mid=s+e>>1;
    return tree[n]=merge(init(n<<1,s,mid),init(n<<1|1,mid+1,e));
}
void updateN(int n,int s,int e,int t){
    if(t<s||t>e)return;
    if(s==e){
        if(tree[n].smax==-1){
            tree[n].smax=now-tree[n].emin-1;
            tree[n].emin=inf;
        }else{
            tree[n].emin=now-tree[n].smax;
            tree[n].smax=-1;
        }
        return;
    }
    int mid=s+e>>1;
    updateN(n<<1,s,mid,t);
    updateN(n<<1|1,mid+1,e,t);
    tree[n]=merge(tree[n<<1],tree[n<<1|1]);
}
node queryM(int n,int s,int e,int l,int r){
    if(s>r||e<l)return {-1,inf};
    if(l<=s&&e<=r)return tree[n];
    int mid=s+e>>1;
    return merge(queryM(n<<1,s,mid,l,r),queryM(n<<1|1,mid+1,e,l,r));
}

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    int n,q,a,b;
    cin>>n>>q>>v;
    init(1,1,n);
    for(now=1;now<=q;now++){
        cin>>v>>a;
        if(v[0]=='q'){
            cin>>b;
            node c=queryM(1,1,n,a,b-1);
            cout<<max(min(now-c.smax,c.emin),0)<<'\n';
        }else{
            updateN(1,1,n,a);
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'node init(int, int, int)':
street_lamps.cpp:19:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int mid=s+e>>1;
      |             ~^~
street_lamps.cpp: In function 'void updateN(int, int, int, int)':
street_lamps.cpp:34:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid=s+e>>1;
      |             ~^~
street_lamps.cpp: In function 'node queryM(int, int, int, int, int)':
street_lamps.cpp:42:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int mid=s+e>>1;
      |             ~^~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20