제출 #1206415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206415		Aiperiii	가로등 (APIO19_street_lamps)	C++20	0 / 100	145 ms	13984 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int t[N*4];
void build(int v,int tl,int tr){
    t[v]=1e18;
    if(tl!=tr){
        int tm=(tl+tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
    }
}
void update(int v,int tl,int tr,int pos,int x){
    if(tl==tr){
        t[v]=x;
        return;
    }
    int tm=(tl+tr)/2;
    if(pos<=tm) update(v*2,tl,tm,pos,x);
    else update(v*2+1,tm+1,tr,pos,x);
    t[v]=max(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
    if(r<tl or tr<l)return -1e18;
    if(l<=tl && tr<=r) return t[v];
    int tm=(tl+tr)/2;
    return max(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    vector <int> t(n+1),sum(n+1);
    string st;
    cin>>st;
    st=' '+st;
    build(1,1,n);
    for(int i=1;i<=n;i++){
        if(st[i]=='1'){
            update(1,1,n,i,0);
        }
    }
    for(int i=1;i<=q;i++){
        string s;
        int a,b;
        cin>>s;
        if(s=="toggle"){
            cin>>a;
            update(1,1,n,a,i);
        }
        else{
            cin>>a>>b;
            int ls=get(1,1,n,a,b);
            if(ls==1e18)cout<<0<<"\n";
            else cout<<i-ls<<"\n";
        }
    }
}
/*

*/

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