Submission #1092216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092216		BLOBVISGOD	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1578 ms	60032 KiB

street_lamps

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int M = 300005; 

template<typename T>
struct fentree{
    vector<T> BIT;
    fentree(int n) : BIT(n+1) {}
    fentree(vector<T> a) : BIT(sz(a)+1){
        rep(i,0,sz(a)) BIT[i+1] = a[i]; // how better?
        rep(i,0,sz(BIT)) if (i+(i&(-i))<sz(BIT)) BIT[i+(i&(-i))] += BIT[i];
    }
    void add(int i, T v){
        for(i++; i<sz(BIT); i+=i&(-i)) BIT[i] += v;
    }
    // for halfopen interval [l,r)
    void rangeadd(int l, int r, T v){
        add(l,v);
        add(r,-v);
    }
    // halfopen query : [0,r)
    T get(int r){
        T ans = {};
        for(;r>0;r-=r&(-r)) ans += BIT[r];
        return ans;
    }
    T pointget(int i){
        T ans = {};
        for(i++;i>0;i-=i&(-i)) ans += BIT[i];
        return ans;
    }
    // returns first index r such that the sum of [0,r] is at least v, or returns n
    int lower_bound(T v){
        T sm = {};
        int at = 0;
        for(int w = 1<<__lg(sz(BIT)); w; w/=2){
            if (at+w<sz(BIT) and sm + BIT[at+w] < v){ 
                at += w;
                sm += BIT[at];
            }
        }
        return at;
    }
    // returns first index r such that the sum of [0,r] is at greater than v, or returns n
    int upper_bound(T v){
        T sm = {};
        int at = 0;
        for(int w = 1<<__lg(sz(BIT)); w; w/=2){
            if (at+w<sz(BIT) and sm + BIT[at+w] <= v){
                at += w;
                sm += BIT[at];
            }
        }
        return at;
    }
    // returns first index r such that the sum of [0,r] is at most v, or returns n
    int lower_bound_decr(T v){
        T sm = {};
        int at = 0;
        for(int w = 1<<__lg(sz(BIT)); w; w/=2){
            if (at+w<sz(BIT) and sm + BIT[at+w] > v){
                at += w;
                sm += BIT[at];
            }
        }
        return at;
    }
    // returns first index r such that the sum of [0,r] is less than v, or returns n
    int upper_bound_decr(T v){
        T sm = {};
        int at = 0;
        for(int w = 1<<__lg(sz(BIT)); w; w/=2){
            if (at+w<sz(BIT) and sm + BIT[at+w] >= v){
                at += w;
                sm += BIT[at];
            }
        }
        return at;
    }
};


const int oo = 1e9;

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,q; cin >> n >> q;
    string s; cin >> s;


    vector<array<int,4>> blocks; // l,r,starttime, endtime+1;
    set<array<int,3>> segs; // l,r,starttime

    vector<array<int,4>> queries; // l,r,time

    for(int i = 0; i < n; ++i){
        if (s[i]=='0') continue;
        int l = i;
        while (i<n and s[i] == '1') i++;
        int r = i;
        segs.insert({l,r,0});
    }

    segs.insert({-oo,-oo,-oo});
    segs.insert({oo,oo,oo});

    // sweep through events;
    rep(i,0,q){
        string t; cin >> t;
        if (t[0]=='q'){
            int l,r; cin >> l >> r;
            l--,r--;
            queries.push_back({l,r,i,sz(queries)});
        }else{
            int x; cin >> x;
            x--;
            if (s[x]=='0'){
                s[x] = '1';
                auto ub = segs.upper_bound({x,x,oo});
                auto lb = ub; lb--;
                array<int,3> ls = *lb;

                int lo = x, hi = x+1;
                // create new block
                if (ls[1] == x){
                    lo = ls[0];
                    blocks.push_back({ls[0],ls[1],ls[2],i+1});
                    segs.erase(lb);
                }

                ub = segs.upper_bound({x,x,oo});
                array<int,3> us = *ub;

                if (us[0] == x+1){
                    hi = us[1];
                    blocks.push_back({us[0],us[1],us[2],i+1});
                    segs.erase(ub);
                }

                segs.insert({lo,hi,i+1});
            }else{
                s[x] = '0';
                auto ub = segs.upper_bound({x,oo,oo});
                ub--;
                // break up this segment
                array<int,3> v = *ub;
                segs.erase(ub);

                blocks.push_back({v[0],v[1],v[2],i+1});

                if (v[0] < x){
                    segs.insert({v[0],x,i+1});
                }if (v[1] > x+1){
                    segs.insert({x+1,v[1],i+1});
                }
            }
        }
    }

    for(auto [l,r,t] : segs){
        if (abs(l) < oo ) blocks.push_back({l,r,t,q});
    }

    vi ans(sz(queries));
    vi eventans;
    
    struct event{
        int t,x,y,id,v;
        bool operator<(event b){
            return t<b.t or (t==b.t and id < b.id);
        }
    };

    // handle linear events and constant events separately
    // r is inverted, so prefix query gives all nodes (l,r) with l>=L, r<=R
    vector<event> Elin, Econ;
    for (auto [l,r,t1,t2] : blocks){
        Elin.push_back({t1,l,M-r,-1,1}); // assume query is closed
        Elin.push_back({t2,l,M-r,-1,-1});
        Econ.push_back({t1,l,M-r,-1,1-t1});
        Econ.push_back({t2,l,M-r,-1,t2-1});
    }

    for (auto [l,r,t,id] : queries){
        Elin.push_back({t,l,M-r,id,0});
        Econ.push_back({t,l,M-r,id,0});
    }

    sort(all(Elin));
    sort(all(Econ));

    fentree<int> fen(M+5);


    auto rec = [&](int ql, int qr, auto&& rec, bool lin, vector<event>& src) -> void {
        if (ql+1 == qr) return;

        int mid = (ql+qr)/2;

        rec(ql,mid,rec,lin, src);
        rec(mid,qr,rec,lin, src);

        // contribute L to R || NOTE CLOSED INTERVALS
        struct ev{
            int x, y, id, v;
            bool operator<(ev b){
                return x<b.x or (x==b.x and id<b.id);
            }
        };

        vector<ev> E;
        rep(i,ql,mid){
            auto& e = src[i];
            if (e.id<0) E.push_back(ev{e.x,e.y,e.id,e.v});
        }
        rep(i,mid,qr){
            auto& e = src[i];
            if (e.id>=0) E.push_back(ev{e.x,e.y,e.id,e.t});
        }

        sort(all(E));

        for(auto& e : E){
            if (e.id<0){
                fen.add(e.y,e.v);
            }else{
                ans[e.id] += fen.get(e.y+1)*(lin?e.v:1);
            }
        }   

        // undo fenwick operations
        for(auto& e : E){
            if (e.id<0){
                fen.add(e.y,-e.v);
            }
        }
    };

    rec(0,sz(Elin),rec,1,Elin);
    rec(0,sz(Econ),rec,0,Econ);

    for(auto c : ans) cout << c << '\n';
}

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