Submission #1257989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257989		M_SH_O	Street Lamps (APIO19_street_lamps)	C++20	0 / 100	5094 ms	22748 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+1) - sum(l);
}

int main(){
    speed;
    ll q;
    cin >> n >> q;
    ll baze = sqrt(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);
    
    vector<pair<pll, ll>> vi, qr;
    vll res(q, 0);
    vll p_;
    
    
    for(int i = 0; i < q; i ++){
        if((i+1) % baze == 0){
            sort(qr);
            bit.clear();
            bit.resize(n+7, 0);
            ll l = 0;
            for(auto j : m){
                while(l < qr.size() && qr[l].fr.fr < j.fr.fr){
                    res[qr[l].se] += range_sum(qr[l].fr.se, n-1);
                    l++;
                }
                add(j.fr.se, j.se);
            }
            for(auto j : vi){
                m[j.fr] += j.se;   
            }
            qr.clear();
            vi.clear();
        }
        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);
                    vi.pb({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);
                    vi.pb({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);
                
                vi.pb({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);*/
            p_.pb(i);
            ll l, r;
            cin >> l >> r;
            l --, r -= 2;
            qr.pb({{l, r}, i});
            for(auto j : vi){
                if(j.fr.fr <= l && r <= j.fr.se) res[i] += 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] += i-p[p1.fr];
            }
            
            
        }
    }
    
    sort(qr);
    bit.clear();
    bit.resize(n+7, 0);
    l = 0;
    for(auto j : m){
        while(l < qr.size() && qr[l].fr.fr < j.fr.fr){
            res[qr[l].se] += range_sum(qr[l].fr.se, n-1);
            l++;
        }
        add(j.fr.se, j.se);
    }
    
    for(int i : p_){
        cout << res[i] << endl;
    }
}

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