Submission #212635

#	Time	Username	Problem	Language	Result	Execution time	Memory
212635		VEGAnn	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2721 ms	319088 KiB

street_lamps

#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pdd pair<ld, ld>
#define ft first
#define sd second
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N = 300100;
const int M = 2 * N;
const int oo = 2e9;
const ll OO = 1e18;
const int md = 998244353;
const int PW = 233;
set<pii> st;
set<pii>::iterator ite;
vector<pii> qr, pts;
string qu, s;
int q, n;
bool state[N];

struct seg_tree{
    vector<int> ys;
    vector<ll> st;

    seg_tree(): ys(0), st(0) {}

    void update(int v, int l, int r, int y, int vl){
        if (ys[l] > y) return;

        if (ys[r] <= y) {
            st[v] += vl;
            return;
        }

        if (l == r) return;

        int md = (l + r) >> 1;
        update(v + v, l, md, y, vl);
        update(v + v + 1, md + 1, r, y, vl);
    }

    ll get(int v, int l, int r, int y){
        ll res = st[v];

        if (l == r) return res;

        int md = (l + r) >> 1;

        if (ys[md + 1] <= y)
            res += get(v + v + 1, md + 1, r, y);
        else res += get(v + v, l, md, y);

        return res;
    }
};

seg_tree seg[4 * N];

void build(int v, int l, int r){
    if (l == r){
        seg[v].ys.PB(pts[l].sd);
        seg[v].st.resize(2);
        return;
    }

    int md = (l + r) >> 1;
    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    merge(all(seg[v + v].ys), all(seg[v + v + 1].ys), back_inserter(seg[v].ys));
    seg[v].st.resize(sz(seg[v].ys) * 4 + 3);
}

void update(int v, int l, int r, int min_x, int max_y, int vl){
    if (pts[r].ft < min_x) return;

    if (pts[l].ft >= min_x) {
        seg[v].update(1, 0, sz(seg[v].ys) - 1, max_y, vl);
        return;
    }

    if (l == r) return;

    int md = (l + r) >> 1;

    update(v + v, l, md, min_x, max_y, vl);
    update(v + v + 1, md + 1, r, min_x, max_y, vl);
}

ll get(int v, int l, int r, int min_x, int max_y){
    ll res = seg[v].get(1, 0, sz(seg[v].ys) - 1, max_y);

    if (l == r) return res;

    int md = (l + r) >> 1;

    if (MP(min_x, max_y) <= pts[md])
        res += get(v + v, l, md, min_x, max_y);
    else res += get(v + v + 1, md + 1, r, min_x, max_y);

    return res;
}

int main() {
#ifdef _LOCAL
//    freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
#else
//    freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif

    cin >> n >> q >> s;

    for (int i = 0; i < n; i++)
        state[i] = s[i] - '0';

    for (int i = 0; i < q; i++){
        cin >> qu;

        if (qu[0] == 'q'){
            int x, y; cin >> x >> y;
            x--; y--;
            qr.PB(MP(x, y));
            pts.PB(MP(x, y));
        } else {
            int x; cin >> x;
            x--;

            qr.PB(MP(x, -228));
        }
    }

    sort(all(pts));
    pts.resize(unique(all(pts)) - pts.begin());

    build(1, 0, sz(pts) - 1);

    for (int i = 0; i <= n;){
        int j = i;
        while (j < n && state[j])
            j++;

        st.insert(MP(i, j));
        i = j + 1;
    }

//    for (pii cr : pts)
//        cerr << cr.ft << " " << cr.sd << '\n';

    int tim = 1;

    for (pii cr : qr) {

//
//        for (auto x : st)
//            cerr << x.ft << " " << x.sd << '\n';
//        cerr << "\n\n";

        if (cr.sd == -228){
            int i = cr.ft;

            if (!state[i]){
                ite = prev(st.upper_bound(MP(i + 1, oo)));
                int lf = (*prev(ite)).ft;
                int rt = (*ite).sd;

                st.erase(MP(lf, i));
                st.erase(MP(i + 1, rt));
                st.insert(MP(lf, rt));

                update(1, 0, sz(pts) - 1, lf, rt, -tim);
                update(1, 0, sz(pts) - 1, lf, i, tim);
                update(1, 0, sz(pts) - 1, i + 1, rt, tim);
            } else {
                pii segm = *(prev(st.upper_bound(MP(i + 1, -oo))));

                st.erase(segm);
                st.insert(MP(segm.ft, i));
                st.insert(MP(i + 1, segm.sd));

                update(1, 0, sz(pts) - 1, segm.ft, segm.sd, tim);
                update(1, 0, sz(pts) - 1, segm.ft, i, -tim);
                update(1, 0, sz(pts) - 1, i + 1, segm.sd, -tim);
            }

            state[i] ^= 1;
        } else {
            ll res = get(1, 0, sz(pts)  - 1, cr.ft, cr.sd);

            pii segm = *prev(st.upper_bound(MP(cr.ft, oo)));

            if (segm.ft <= cr.ft && segm.sd >= cr.sd)
                res += tim;

            cout << res << '\n';
        }

        tim++;
    }

    return 0;
}

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