제출 #721750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721750		victor_gao	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	222 ms	11364 KiB

street_lamps

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 300015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct segtree{
    int seg[4*N];
    void change(int l,int r,int i,int p,int c){
        if (l==r){
            seg[i]=c;
            return;
        }
        int mid=(l+r)>>1;
        if (p<=mid) change(l,mid,2*i,p,c);
        else change(mid+1,r,2*i+1,p,c);
        seg[i]=max(seg[2*i],seg[2*i+1]);
    }
    int query(int l,int r,int i,int ll,int rr){
        if (ll<=l&&rr>=r) return seg[i];
        int mid=(l+r)>>1;
        if (rr<=mid) return query(l,mid,2*i,ll,rr);
        else if (ll>mid) return query(mid+1,r,2*i+1,ll,rr);
        else return max(query(l,mid,2*i,ll,rr),query(mid+1,r,2*i+1,ll,rr));
    }
}seg;
int n,q;
bool arr[N];
signed main(){
    fast
    cin>>n>>q;
    for (int i=1;i<=n;i++){
        char c; cin>>c;
        arr[i]=c-'0';
        if (arr[i])
            seg.change(1,n,1,i,0);
        else seg.change(1,n,1,i,1e9);
    }
    for (int t=1;t<=q;t++){
        string str; cin>>str;
        if (str=="toggle"){
            int p; cin>>p;
            arr[p]^=1;
            seg.change(1,n,1,p,t);
        }
        else {
            int l,r; cin>>l>>r;
            int last=seg.query(1,n,1,l,r-1);
            if (last>1e8) cout<<0<<'\n';
            else cout<<t-last<<'\n';
        }
    }
}

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