제출 #1208359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208359		avohado	가로등 (APIO19_street_lamps)	C++20	20 / 100	163 ms	10936 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 300005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
int n, m;
string s;
int tree[maxn*4], mtree[maxn*4];
void bt(int v, int tl, int tr){
    mtree[v]=-1;
    if(tl==tr){
        tree[v]=s[tl]-'0';
        return;
    }
    int tm=(tl+tr)/2;
    bt(v*2, tl, tm);bt(v*2+1, tm+1, tr);
    tree[v]=(tree[v*2]&tree[v*2+1]);
}
void upd(int v, int l, int tl, int tr, int x, int j){
    if(tl==tr){
        tree[v]=x;
        mtree[v]=j;
        return;
    }
    int tm=(tl+tr)/2;
    mtree[v]=j;
    if(tm<l){
        upd(v*2+1, l, tm+1, tr, x, j);
    }else{
        upd(v*2, l, tl, tm, x, j);
    }
    tree[v]=(tree[v*2]&tree[v*2+1]);
}
pair<int,int> res(int v, int l, int r, int tl, int tr){
    if(tl>r||l>tr){
        return {1, -1};
    }
    if(l<=tl&&tr<=r){
        return {tree[v], mtree[v]};
    }
    pair<int, int> a=res(v*2, l, r, tl, (tl+tr)/2), b=res(v*2+1, l, r,(tl+tr)/2+1, tr);
    return {(a.f&b.f), max(a.s, b.s)};
}
void solve(){
    cin >> n >> m;
    cin >> s;
    string s1;
    bt(1, 0, n-1);
    for(int i=0; i<m; i++){
        cin >> s1;
        if(s1[0]=='q'){
            int l, r;
            cin >> l >> r;
            l--; r-=2;
            pair<int, int> a=res(1, l, r, 0, n-1);
            if(a.f==1){
                cout << i-a.s;
            }else{
                cout <<0;
            }
            cout << "\n";
        }else{
            int x;
            cin >> x;
            upd(1, x-1, 0, n-1, (1^(s[x-1]-'0')), i);
            s[x-1]=(1^(s[x-1]-'0'))+'0';
        }
    }
}
int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int t=1;
    //cin >> t;
    while(t--){
        solve();
        cout << "\n";
    }
    return 0;
}

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