제출 #1092424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1092424		mispertion	가로등 (APIO19_street_lamps)	C++17	100 / 100	1701 ms	216112 KiB

street_lamps

#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 3e5 + 1;
const int M = 50 + 1;
const int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 31;

int mult(int a, int b) {
    return a * 1LL * b % mod;
}

int sum(int a, int b) { 
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}

ll binpow(ll a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}

struct fenwick{
    vector<int> f;
    fenwick(int n){
        f.assign(n + 1, 0);
    }

    fenwick(){

    }

    void add(int i, int x){
        for(; i < sz(f); i = (i | (i + 1)))
            f[i] += x;
    }

    int get(int r){
        int ret = 0;
        for(; r >= 0; r = (r & (r + 1)) - 1)
            ret += f[r];
        return ret;
    }

    int get(int l, int r){
        return get(r) - get(l - 1);
    }
};

struct segtree{
    fenwick up[4 * N];
    vector<int> mr[4 * N];

    void build(int v, int tl, int tr, vector<pii> &a){
        if(tl == tr){
            mr[v] = {a[tl].S};
            up[v] = fenwick(1);
        }else{
            int tm = (tl + tr) / 2;
            build(2 * v, tl, tm, a);
            build(2 * v + 1, tm + 1, tr, a);
            mr[v] = {};
            int lu = 0, ru = 0;
            while(lu < sz(mr[2 * v]) || ru < sz(mr[2 * v + 1])){
                if(lu == sz(mr[2 * v])){
                    mr[v].pb({mr[2 * v + 1][ru]});
                    ru++;
                }else if(ru == sz(mr[2 * v + 1])){
                    mr[v].pb({mr[2 * v][lu]});
                    lu++;
                }else if(mr[2 * v][lu] > mr[2 * v + 1][ru]){
                    mr[v].pb(mr[2 * v + 1][ru]);
                    ru++;
                }else{
                    mr[v].pb({mr[2 * v][lu]});
                    lu++;
                }
            }
            up[v] = fenwick(tr - tl + 1);
        }
    }

    void upd(int v, int tl, int tr, int l, int r, int l1, int r1, int x){
        if(tl > r || l > tr) return;
        if(l <= tl && tr <= r){
            int l2 = lower_bound(all(mr[v]), l1) - mr[v].begin();
            int r2 = upper_bound(all(mr[v]), r1) - mr[v].begin();
            up[v].add(l2, x);
            up[v].add(r2, -x);
            return;
        }
        int tm = (tl + tr) / 2;
        upd(2 * v, tl, tm, l, r, l1, r1, x);
        upd(2 * v + 1, tm + 1, tr, l, r, l1, r1, x);
    }

    int get(int v, int tl, int tr, int i, int ps){
        if(tl == tr){
            return up[v].get(0);
        }
        int tm = (tl + tr) / 2;
        int ha = lower_bound(all(mr[v]), ps) - mr[v].begin();
        int sm = up[v].get(ha);
        if(i <= tm){
            return get(2 * v, tl, tm, i, ps) + sm;
        }else{
            return get(2 * v + 1, tm + 1, tr, i, ps) + sm;
        }
    }
};

int n, q, a[N];
pair<int, pii> qr[N];
vector<pii> sgs;

void solve(){
    cin >> n >> q;
    string ini;
    cin >> ini;
    for(int i = 1; i <= n; i++)
        a[i] = ini[i - 1] - '0';
    fenwick f = fenwick(n);
    for(int i = 1; i <= n; i++)
        f.add(i, a[i]);
    for(int i = 1; i <= q; i++){
        string tp;
        cin >> tp;
        if(tp == "toggle"){
            int j;
            cin >> j;
            qr[i] = {1, {j, 0}};
        }else{
            int a, b;
            cin >> a >> b;
            b--;
            qr[i] = {2, {a, b}};
            sgs.pb({a, b});
        }
    }
    sort(all(sgs));
    segtree tr;
    tr.build(1, 0, sz(sgs) - 1, sgs);
    for(int i = 1; i <= q; i++){
        if(qr[i].F == 1){
            int ps = qr[i].S.F;
            int lo = 0, hi = ps;
            while(lo + 1 < hi){
                int m = (lo + hi) / 2;
                if(f.get(m, ps - 1) != (ps - m)){
                    lo = m;
                }else{
                    hi = m;
                }
            }
            int lu = hi;
            lo = ps, hi = n + 1;
            while(lo + 1 < hi){
                int m = (lo + hi) / 2;
                if(f.get(ps + 1, m) != m - ps)
                    hi = m;
                else
                    lo = m;
            }
            int ru = lo;
            if(a[ps] == 0){
                a[ps] = 1;
                f.add(ps, 1);
                int l = lower_bound(all(sgs), make_pair(lu, -1LL)) - sgs.begin();
                int r = upper_bound(all(sgs), make_pair(ps, infi)) - sgs.begin() - 1;
                tr.upd(1, 0, sz(sgs) - 1, l, r, ps, ru, -i);
            }else{
                a[ps] = 0;
                f.add(ps, -1);
                int l = lower_bound(all(sgs), make_pair(lu, -1LL)) - sgs.begin();
                int r = upper_bound(all(sgs), make_pair(ps, infi)) - sgs.begin() - 1;
                tr.upd(1, 0, sz(sgs) - 1, l, r, ps, ru, i);
            }
        }else{
            int a = qr[i].S.F, b = qr[i].S.S;
            int ad = ((f.get(a, b) == b - a + 1) ? i : 0);
            int ps = lower_bound(all(sgs), make_pair(a, b)) - sgs.begin();
            cout << tr.get(1, 0, sz(sgs) - 1, ps, sgs[ps].S) + ad << '\n';
        }
    }
}   

signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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