Submission #1257959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257959		M_SH_O	Street Lamps (APIO19_street_lamps)	C++20	20 / 100	5093 ms	21848 KiB

street_lamps

#include <bits/stdc++.h>
//#include "rainbow.h"

#define ll long long
#define ll1 long long
#define ull unsigned long long
#define dou long double
#define str string
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vbool vector<bool>
#define vstr vector<str>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
#define endl "\n"
#define fr first
#define se second
// #define sortcmp(a) sort(a.begin(), a.end(), cmp)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
//using namespace __gnu_pbds;

const ll INF = 1e18;
const int lg = 20;

mt19937 rng(time(0));
ll randll(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(rng);
}

ll n;
vll bit;

void add(int i, ll val) {
    for (; i < n; i += i & -i)
        bit[i] += val;
}

ll sum(int i) {
    ll res = 0;
    for (; i > 0; i -= i & -i)
        res += bit[i];
    return res;
}

ll range_sum(int l, int r) {
    return sum(r) - sum(l - 1);
}

int main(){
    speed;
    ll q;
    cin >> n >> q;
    str s;
    cin >> s;
    set<pll> v;
    ll l = -1;
    for(int i = 0; i < n; i ++){
        if(s[i] == '1'){
            if(l == -1) l = i;
        }
        else{
            if(l != -1){
                v.insert({l, i-1});
                l = -1;
            }
        }
    }
    if(l != -1) v.insert({l, n-1});
    map<pll, ll> m;
    vll p(n+7, -1);
    
    for(int i = 0; i < q; i ++){
        str s1;
        cin >> s1;
        if(s1 == "toggle"){
            ll x;
            cin >> x;
            x --;
            if(s[x] == '0'){
                ll l = x, r = x;
                if(v.size() && v.lower_bound({x, -1}) != v.begin() && (*--v.lower_bound({x, -1})).se == x-1){
                    pll p1 = *--v.lower_bound({x, -1});
                    v.erase(p1);
                    m[p1] += i-p[p1.fr];
                    l = p1.fr;
                }
                if(v.lower_bound({x, -1}) != v.end() && (*v.lower_bound({x, -1})).fr == x+1){
                    pll p1 = *v.lower_bound({x, -1});
                    v.erase(p1);
                    m[p1] += i-p[p1.fr];
                    r = p1.se;
                }
                p[l] = i;
                v.insert({l, r});
                s[x] = '1';
            }
            else{
                pll p1 = *--v.upper_bound({x, INF});
                v.erase(p1);
                
                m[p1] += i-p[p1.fr];
                if(p1.fr != x){
                    p[p1.fr] = i;
                    v.insert({p1.fr, x-1});
                }
                if(p1.se != x){
                    p[x+1] = i;
                    v.insert({x+1, p1.se});
                }
                
                s[x] = '0';
            }
        }
        else{
            /*bit.clear();
            bit.resize(n+7, 0);*/
            ll l, r;
            cin >> l >> r;
            l --, r -= 2;
            ll res = 0;
            for(auto j : m){
                if(j.fr.fr > l) break;
                if(j.fr.se >= r) res += j.se;
            }
            if(v.upper_bound({l, INF}) != v.begin() && v.size()){
                pll p1 = *--v.upper_bound({l, INF});
                if(p1.se >= r) res += i-p[p1.fr];
            }
            
            
            cout << res << endl;
        }
    }
}

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