Submission #405557

#	Time	Username	Problem	Language	Result	Execution time	Memory
405557		Jarif_Rahman	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	943 ms	74336 KiB

street_lamps

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
struct BIT{
    int n;
    vector<ll> sm;
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void upd(int in, int x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    ll sum(int in){
        in++;
        ll s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
    ll sum(int l, int r){
        return sum(r)-(l == 0? 0:sum(l-1));
    }
};
struct segtree{
    int k, n;
    vector<int> mn;
    segtree(int _n){
        n = _n;
        k = 1;
        while(k < n) k*=2;
        k*=2;
        mn.resize(k, 1);
    }
    void toggle(int in){
        in+=k/2;
        mn[in] = !mn[in];
        in/=2;
        while(in > 0){
            mn[in] = min(mn[2*in], mn[2*in+1]);
            in/=2;
        }
    }
    int get(int in){
        return mn[in+k/2];
    }
    int find(int in, int nd, int a, int b){
        if(mn[nd] == 1) return -1;
        if(in > b) return -1;
        if(a == b) return a;
        int md = (a+b)/2;
        int x;
        return (x = find(in, 2*nd, a, md)) == -1 ?  find(in, 2*nd+1, md+1, b) : x;
    }
    int find(int in){
        int x = find(in, 1, 0, k/2-1);
        if(x == -1) x = n;
        x--;
        return x;
    }
    int rfind(int in, int nd, int a, int b){
        if(mn[nd] == 1) return -1;
        if(in < a) return -1;
        if(a == b) return a;
        int md = (a+b)/2;
        int x;
        return (x = rfind(in, 2*nd+1, md+1, b)) == -1 ?  rfind(in, 2*nd, a, md) : x;
    }
    int rfind(int in){
        int x = rfind(in, 1, 0, k/2-1);
        x++;
        return x;
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n >> q;
    segtree seg(n);
    for(int i = 0; i < n; i++){
        char c; cin >> c;
        if(c == '0') seg.toggle(i);
    }
    vector<int> tg;
    vector<tuple<int, int, int>> query;
    for(int i = 0; i < q; i++){
        str tt; cin >> tt;
        if(tt == "toggle"){
            int in; cin >> in; in--;
            tg.pb(in);
        }
        else{
            int a, b; cin >> a >> b; a--, b-=2;
            query.pb({a, b, query.size()});
        }
    }
    map<pair<int, int>, int> mp;
    struct segment{
        int l, r, init, vl;
        bool closed;
        segment(int _l, int _r, int _init){
            l = _l, r = _r, init = _init, vl = -1, closed = 0;
        }
        void close(int e){
            vl = e-init+1;
            closed = 1;
        }
        bool operator<(segment a){
            return make_pair(r, l) < make_pair(a.r, a.l);
        }
    };
    vector<segment> segments;
    auto seg_add = [&](int l, int r, int init){
        mp[{l, r}] = segments.size();
        segments.pb(segment(l, r, init));   
    };
    auto seg_rem = [&](int l, int r, int tt){
        int pos = mp[{l, r}];
        mp[{l, r}] = -1;
        segments[pos].close(tt);
    };
    int sss = -1, eee = 0;
    for(int i = 0; i < n; i++){
        if(seg.get(i) == 0){
            sss = -1;
            continue;
        }
        if(sss == -1) sss = i, eee = i-1;
        eee++;
        if(i != n-1 && seg.get(i+1) == 1) continue;
        seg_add(sss, eee, 0);
    }
    for(int tt = 1; tt <= tg.size(); tt++){
        int in = tg[tt-1];
        if(seg.get(in) == 0){
            if(in > 0 && seg.get(in-1) == 1){
                int l = seg.rfind(in-1);
                seg_rem(l, in-1, tt-1);
            }
            if(in+1 < n && seg.get(in+1) == 1){
                int r = seg.find(in+1);
                seg_rem(in+1, r, tt-1);
            }
            seg.toggle(in);
            int l = seg.rfind(in), r = seg.find(in);
            seg_add(l, r, tt);
        }
        else{
            int l = seg.rfind(in), r = seg.find(in);
            seg_rem(l, r, tt-1);
            seg.toggle(in);
            if(in > 0 && seg.get(in-1) == 1){
                int l = seg.rfind(in-1);
                seg_add(l, in-1, tt);
            }
            if(in+1 < n && seg.get(in+1) == 1){
                int r = seg.find(in+1);
                seg_add(in+1, r, tt);
            }
        }
    }
    //for(auto sg: segments) cerr << sg.l << " " << sg.r << " " << sg.init << " " << sg.closed << " d\n";
    vector<vector<int>> sg2(n);
    for(int i = 0; i < segments.size(); i++){
        if(segments[i].closed) continue;
        sg2[segments[i].l].pb(segments[i].r);
        segments[i].close(tg.size());
    }
    vector<vector<segment>> rrs(n);
    vector<vector<tuple<int, int, int>>> rrq(n);
    for(int i = 0; i < segments.size(); i++){
        rrs[segments[i].l].pb(segments[i]);
    }
    for(int i = 0; i < query.size(); i++) rrq[get<0>(query[i])].pb(query[i]);

    BIT bit(n);

    vector<ll> ans(query.size(), 0);
    for(int i = 0; i < n; i++){
        for(auto sg: rrs[i]) bit.upd(sg.r, sg.vl);
        for(auto [a, b, in]: rrq[i]) ans[in]+=bit.sum(b, n-1);
    }
    bit = BIT(n);
    for(int i = 0; i < n; i++){
        for(int r: sg2[i]) bit.upd(r, 1);
        for(auto [a, b, in]: rrq[i]) ans[in]+=bit.sum(b, n-1)*in;
    }
    for(ll x: ans) cout << x << "\n";
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:137:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(int tt = 1; tt <= tg.size(); tt++){
      |                     ~~~^~~~~~~~~~~~
street_lamps.cpp:168:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |     for(int i = 0; i < segments.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:175:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for(int i = 0; i < segments.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:178:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for(int i = 0; i < query.size(); i++) rrq[get<0>(query[i])].pb(query[i]);
      |                    ~~^~~~~~~~~~~~~~

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