제출 #591730

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

street_lamps

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define all(x) begin(x), end(x)
#define mp make_pair
#define pb push_back
#define sz(x) ((int) size(x))
const int infI = 1e9 + 7;
const ll infL = 3e18;
 
template<typename T>
struct SegTreeDownMin {
    const T MAX = numeric_limits<T>::max() / 2;
    vector <T> t;
    int sz;
 
    void init(int n, T x = 0) {
        sz = n;
        t.assign(sz << 1, x);
    }
 
    void st(int i, T v) {
        int x = i + sz;
        t[x] = v;
        x >>= 1;
        while (x) {
            t[x] = min(t[x << 1], t[x << 1 | 1]);
            x >>= 1;
        }
    }
 
    T get(int l, int r) { // [l, r)
        T ans = MAX;
        l += sz;
        r += sz;
        while (l < r) {
            if (l & 1) {
                //it is a right child
                ans = min(ans, t[l++]);
            }
            if (r & 1) {
                //this is a left child
                ans = min(ans, t[--r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return ans;
    }
 
};
 
template<typename T>
void make_uniq(vector<T> &v) {
    sort(all(v));
    v.resize(unique(all(v)) - begin(v));
}
 
struct Fenwick {
    vector<vector<ll>> t;
    vector<vector<int>> yy;
    int n;
 
 
    Fenwick() = default;
 
    Fenwick(int n) {
        init(n);
    }
 
    void init(int a) {
        n = a;
        yy.resize(n);
        for (int i = 0; i < n; ++i) yy[i].clear();
        t.resize(n);
    }
 
    void fake_add(int x, int y) {
        assert(x < n);
        assert(x >= 0);
        for (int i = x; i < n; i |= (i + 1))
            yy[i].pb(y);
    }
 
    void build() {
        for (int i = 0; i < n; ++i) {
            make_uniq(yy[i]);
            t[i].assign(sz(yy[i]) + 2, 0);
        }
    }
 
    void add(int x, int y, int v) {
        assert(x < n);
        assert(x >= 0);
        for (int i = x; i < n; i |= (i + 1))
            for (int j = lower_bound(all(yy[i]), y) - begin(yy[i]); j < sz(yy[i]); j |= (j + 1))
                t[i][j] += v;
    }
 
    ll get(int x, int y) {
        ll ans = 0;
        assert(x < n);
        for (int i = x; i > -1; i = ((i + 1) & i) - 1)
            for (int j = upper_bound(all(yy[i]), y) - begin(yy[i]) - 1; j > -1; j = ((j + 1) & j) - 1)
                ans += t[i][j];
        return ans;
    }
 
    void add(int x1, int y1, int x2, int y2, int v) {
        add(x1, y1, v);
        add(x1, y2 + 1, -v);
        add(x2 + 1, y1, -v);
        add(x2 + 1, y2 + 1, v);
    }
 
    void fake_add(int x1, int y1, int x2, int y2) {
        fake_add(x1, y1);
        fake_add(x1, y2 + 1);
        fake_add(x2 + 1, y1);
        fake_add(x2 + 1, y2 + 1);
    }
 
};
 
struct binary_fen {
    vector<int> t;
    int n;
 
    binary_fen() = default;
 
    binary_fen(int a) {
        n = a + 1;
        t.assign(n, 0);
    }
 
    void add(int i, int v) {
        assert(i > 0);
        for (; i < n; i += i & -i) {
            t[i] += v;
        }
    }
 
    int get(int i) {
        int ans = 0;
        for (; i > 0; i -= i & -i)
            ans += t[i];
        return ans;
    }
 
    int kth(int k) {
        if (k == 0) return -1;
        int i = 0;
        for (int j = 19; j >= 0; --j) {
            if (i + (1 << j) < n && t[i + (1 << j)] < k) {
                i += (1 << j);
                k -= t[i];
            }
        }
        return i;
    }
 
    pair<int, int> get_seg(int i) {
        int sump = get(i);
        int L = kth(sump) + 1;
        int R = kth(sump + 1);
        return mp(L, R);
    }
 
};
 
const int N = 600001;
 
int a[N], b[N], arr[N], L[N], R[N];
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    Fenwick t(n + 2);
    binary_fen fn(n);
    string ss;
    cin >> ss;
    vector<int> LL(n), RR(n);
    int sta = 0;
    for (int i = 0; i < n; ++i) {
        if (ss[i] == '1') {
            a[sta] = i;
            b[sta] = -1;
            ++sta;
        }
    }
    q += sta;
    for (int i = sta; i < q; ++i) {
        string s;
        cin >> s;
        if (s == "toggle") {
            cin >> a[i];
            --a[i];
            b[i] = -1;
        } else {
            cin >> a[i] >> b[i];
            --a[i], --b[i];
        }
    }
    for (int i = 1; i <= n; ++i) fn.add(i, 1);
    for (int i = 0; i < q; ++i) {
        if (b[i] == -1) {
            if (arr[a[i]] == 1) {
                tie(L[i], R[i]) = fn.get_seg(a[i]);
                t.fake_add(L[i], a[i] + 1, a[i], R[i]);
                arr[a[i]] = 0;
                fn.add(a[i] + 1, 1);
            } else {
                fn.add(a[i] + 1, -1);
                arr[a[i]] = 1;
                tie(L[i], R[i]) = fn.get_seg(a[i]);
                t.fake_add(L[i], a[i] + 1, a[i], R[i]);
            }
        }
    }
    t.build();
    SegTreeDownMin<int> st;
    st.init(n);
    memset(arr, 0, sizeof(arr));
    for (int i = 0; i < q; ++i) {
        int tim;
        if (i < sta) tim = q - sta;
        else tim = q - i - 1;
        if (b[i] == -1) {
            if (arr[a[i]] == 1) {
                arr[a[i]] = 0;
                st.st(a[i], 0);
                t.add(L[i], a[i] + 1, a[i], R[i], -tim);
            } else {
                arr[a[i]] = 1;
                st.st(a[i], 1);
                t.add(L[i], a[i] + 1, a[i], R[i], tim);
            }
        } else {
            if (st.get(a[i], b[i])) {
                cout << t.get(a[i], b[i]) - tim << '\n';
            } else {
                cout << t.get(a[i], b[i]) << '\n';
            }
        }
    }
    return 0;
}

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