Submission #1196867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196867		cpdreamer	Street Lamps (APIO19_street_lamps)	C++20	20 / 100	478 ms	8044 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define V vector
#define pb push_back
struct segtree {
private:
    struct node {
        int maxd;
    };
    node single(int v) {
        return {v};
    }
    node neutral={INT_MIN};
    node merge(node a,node b) {
        return {max(a.maxd,b.maxd)};
    }
public:
    int size;
    V<node>query;
    void init(int n) {
        size=1;
        while (size<n)size*=2;
        query.assign(2*size,{INT_MIN});
    }
    void set(int i,int v,int x,int lx,int rx){
        if (rx-lx==1) {
            query[x]=single(v);
            return;
        }
        int m=(lx+rx)/2;
        if (i<m)
            set(i,v,2*x+1,lx,m);
        else
            set(i,v,2*x+2,m,rx);
        query[x]=merge(query[2*x+1],query[2*x+2]);
    }
    void set(int i,int v) {
        set(i,v,0,0,size);
    }
    node calc(int l,int r,int x,int lx,int rx) {
        if (lx>=r || rx<=l)return neutral;
        if (l<=lx && rx<=r)return query[x];
        int m=(lx+rx)/2;
        node a=calc(l,r,2*x+1,lx,m);
        node b=calc(l,r,2*x+2,m,rx);
        return merge(a,b);
    }
    int calc(int l,int r) {
        return calc(l,r,0,0,size).maxd;
    }
};
void solve() {
    int n;
    cin>>n;
    int q;
    cin>>q;
    string s;
    cin>>s;
    V<int>ans(n,-1);
    segtree tree;
    tree.init(n);
    for (int i=0;i<n;i++) {
        if (s[i]=='1') {
            tree.set(i,0);
        }
        else {
            tree.set(i,INT_MAX);
        }
    }
    for (int i=1;i<=q;i++) {
        string t;
        cin>>t;
        if (t=="query") {
            int l,r;
            cin>>l>>r;
            l--,r--;
            if (tree.calc(l,r)==INT_MAX) {
                cout<<0<<endl;
            }
            else {
                cout<<i-tree.calc(l,r)<<endl;
            }
        }
        else {
            int a;
            cin>>a;
            a--;
            tree.set(a,i);
        }
    }
 }
 int main() {
   solve();


}

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