Submission #385676

#	Time	Username	Problem	Language	Result	Execution time	Memory
385676		valerikk	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	4295 ms	246332 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

#define y1 y1111

#define mp make_pair
#define F first
#define S second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)a.size())
#define forn(i, n) for (int i = 0; i < (n); ++i)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1.1e9;
const ll INFL = 1.1e18;

const int N = 3e5 + 7;

struct Upd {
    int x, y, type;
};

int n, q;
string s, ss;
vector<Upd> upds[N];
pii qr[N];
set<int> st;
vector<int> yy[N];
vector<ll> f[N];
vector<int> cnt[N];

void innerUpd(int pp, int y, int t, int tp) {
    y = lower_bound(all(yy[pp]), y) - yy[pp].begin();
    for (int i = y + 1; i <= sz(yy[pp]); i += i & -i) {
        f[pp][i] += tp * t;
        cnt[pp][i] += tp;
    }
}

void upd(int x, int y, int t, int tp) {
    for (int i = x + 1; i < N; i += i & -i) innerUpd(i, y, t, tp);
}

ll innerGet(int pp, int y, int t) {
    y = lower_bound(all(yy[pp]), y) - yy[pp].begin();
    ll res = 0;
    for (int i = y; i > 0; i -= i & -i) res += cnt[pp][i] * t - f[pp][i];
    return res;
}

ll get(int x, int y, int t) {
    ll res = 0;
    for (int i = x; i > 0; i -= i & -i) res += innerGet(i, y, t);
    return res;
}

void addY(int x, int y) {
    for (int i = x + 1; i < N; i += i & -i) yy[i].pb(y);
}

void adds(int t, int x1, int y1, int x2, int y2, int type) {
    ++x2, ++y2;
    upds[t].pb({x1, y1, type});
    upds[t].pb({x1, y2, -type});
    upds[t].pb({x2, y1, -type});
    upds[t].pb({x2, y2, type});
}

void toggle(int i, int t) {
    int prv = *prev(st.lower_bound(i)), nxt = *st.upper_bound(i);
    int type = s[i] == '0' ? 1 : -1;
    adds(t, prv + 1, i + 1, i, nxt, type);
    if (s[i] == '0') {
        s[i] = '1';
        st.erase(i); 
    } else {
        s[i] = '0';
        st.insert(i);
    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q >> ss;
    s = string(n, '0');
    for (int i = -1; i <= n; ++i) st.insert(i);
    forn(i, n) {
        if (ss[i] == '1') {
            toggle(i, 0);
        }
    }
    for (int t = 0; t <= q; ++t) qr[t] = {-1, -1};
    for (int t = 1; t <= q; ++t) {
        string type;
        cin >> type;
        if (type == "toggle") {
            int i;
            cin >> i;
            --i;
            toggle(i, t);
        } else {
            int a, b;
            cin >> a >> b;
            --a, --b;
            qr[t] = {a, b};
        }
    }
    
    for (int t = 0; t <= q; ++t) {
        for (auto u : upds[t]) {
            addY(u.x, u.y);
        }
    }
    
    for (int i = 0; i < N; ++i) {
        sort(all(yy[i]));
        yy[i].erase(unique(all(yy[i])), yy[i].end());
        f[i] = vector<ll>(sz(yy[i]) + 1, 0ll);
        cnt[i] = vector<int>(sz(yy[i]) + 1, 0);
    }
    
    for (int t = 0; t <= q; ++t) {
        for (auto u : upds[t]) upd(u.x, u.y, t, u.type);
        if (qr[t].F != -1) cout << get(qr[t].F + 1, qr[t].S + 1, t) << "\n";
    }
    return 0;
}

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