Submission #1186168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186168		Gray	Street Lamps (APIO19_street_lamps)	C++20	80 / 100	5093 ms	74720 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

struct SegTree{
    struct node{
        ll mx, mn, upd, tag;
    };
    vector<node> t;
    ll sz, rsz;
    SegTree(ll N){
        sz=N*4; rsz=N; t.resize(sz);
    }
    void preprocess(ll tl, ll tr, ll v){
        if (t[v].tag){
            t[v].tag=0; t[v].mx=t[v].mn=t[v].upd;
            if (tl!=tr){
                t[v*2].upd=t[v*2+1].upd=t[v].upd;
                t[v*2].tag=t[v*2+1].tag=1;
            }
        }
    }
    node merge(node l, node r){
        return {max(l.mx, r.mx), min(l.mn, r.mn), 0, 0};
    }
    void update(ll tl, ll tr, ll v, ll l, ll r, ll x){
        preprocess(tl, tr, v);
        if (tl==l and tr==r){
            t[v].upd=x; t[v].tag=1;
            preprocess(tl, tr, v);
        }else if (l>r) return;
        else{
            ll tm = (tl+tr)/2;
            update(tl, tm, v*(2), l, min(r, tm), x);
            update(tm+1, tr, v*2+1, max(l, tm+1), r, x);
            t[v] = merge(t[v*2], t[v*2+1]);
        }
    }
    void update(ll l, ll r, ll x){
        // cout << l << " - " << r << " <- " << x << ln;
        update(0, rsz-1, 1, l, r, x);
    }
    ll query(ll tl, ll tr, ll v, ll l, ll r, ll x){
        preprocess(tl, tr, v);
        if (l<=tl and tr<=r and t[v].mx<x){
            return tr-tl+1;
        }else if (l>tr or r<tl or (t[v].mn>=x)){
            return 0;
        }else{
            ll tm = (tl+tr)/2;
            return query(tl, tm, v*2, l, r, x)+query(tm+1, tr, v*2+1, l, r, x);
        }
    }
    ll query(ll l, ll r, ll x){
        // cout << l << " - " << r << " -> " << x << " = ";
        // cout << query(0, rsz-1, 1, l, r, x) << ln;
        return query(0, rsz-1, 1, l, r, x);
    }
};


void solve(){
    ll n, q; cin >> n >> q;
    vector<ll> state(n+1, -1);
    for (ll i=1; i<=n; i++){
        char x; cin >> x; if (x=='0') state[i]=1;
    }
    vector<vector<pair<ll, ll>>> events(n+1);
    vector<vector<pair<ll, ll>>> qry(n+1);
    for (ll i=1; i<=q; i++){
        string typ; cin >> typ;
        if (typ=="toggle"){
            ll j; cin >> j;
            if (state[j]==-1){
                state[j]=i+1;
            }else{
                events[j].push_back({state[j], i});
                state[j]=-1;
            }
        }else{
            ll a, b; cin >> a >> b;
            qry[b-1].push_back({a, i});
        }
    }
    for (ll i=1; i<=n; i++){
        if (state[i]!=-1){
            events[i].push_back({state[i], q});
        }
    }
    SegTree tr(q+1); vector<ll> qs(q+1, -1);
    for (ll i=1; i<=n; i++){
        // cout << "Came " << i << ln;
        for (auto [l, r]:events[i]){
            tr.update(l, r, i);
        }
        for (auto [l, j]:qry[i]){
            qs[j] = tr.query(1, j, l);
        }
    }
    for (ll i=1; i<=q; i++) if (qs[i]!=-1) cout << qs[i] << ln;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll __c=1; __c<=t; __c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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