Submission #405442

#	Time	Username	Problem	Language	Result	Execution time	Memory
405442		Jarif_Rahman	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	5092 ms	13908 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 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(l, r) < make_pair(a.l, a.r);
        }
    };
    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 = 0; tt < tg.size(); tt++){
        int in = tg[tt];
        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-1);
            }
            if(in+1 < n && seg.get(in+1) == 1){
                int r = seg.find(in+1);
                seg_add(in+1, r, tt-1);
            }
        }
    }
    vector<int> ans(query.size());
    for(int qq = 0; qq < query.size(); qq++){
        auto [a, b, in] = query[qq];
        ans[in] = 0;
        for(int i = 0; i < segments.size(); i++){
            if(segments[i].closed) ans[in]+=segments[i].vl;
            else ans[in]+=(int)(tg.size())+qq-segments[i].init+1;
        }
    }
    for(int x: ans) cout << x << "\n";
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:116:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(int tt = 0; tt < tg.size(); tt++){
      |                     ~~~^~~~~~~~~~~
street_lamps.cpp:146:24: 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]
  146 |     for(int qq = 0; qq < query.size(); qq++){
      |                     ~~~^~~~~~~~~~~~~~
street_lamps.cpp:149:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for(int i = 0; i < segments.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~

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