Submission #1280144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280144		magepetrus	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	3182 ms	315232 KiB

street_lamps

// #define PRAGMAS
// #define OSET
// #define INTERACTIVE

#ifdef PRAGMAS //pragmas
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

#include <bits/stdc++.h>
using namespace std;

#ifdef OSET // Ordered set
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T, class B = null_type> using ordered_set = tree<T, B, less<T>, rb_tree_tag,  tree_order_statistics_node_update>;
template<class T> struct ordered_multiset{
	ordered_set<pair<T, int>> o; int c;
	ordered_multiset():c(0){}
	unsigned order_of_key(T x){return o.order_of_key({x, -1});}
	const T* find_by_order(int p){return &(*o.find_by_order(p)).first;}
	void insert(T x){o.insert({x, c++});}
	void erase(T x){o.erase(o.lower_bound({x, 0}));}
	unsigned size(){return o.size();}
	const T* lower_bound(T x){return &(*o.lower_bound({x, 0})).first;}
	const T* upper_bound(T x){return &(*o.upper_bound({x, c})).first;}
};
#endif

#ifndef INTERACTIVE
#define endl '\n'
#endif

#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)

#define inbounds(x, l, r) ((l) <= (x) && (x) <= (r))
#define L0(res...) [&](){ return res; }
#define L1(res...) [&](auto const & x){ return res; }
#define L2(res...) [&](auto const & x, auto const& y){ return res; }
#define sz(x) (int)x.size()

//debug:
#ifdef LOCAL
#define debug(x...) cout<<"["#x"]: ",[](auto...$){((cout<<$<<"; "),...);}(x),cout<<endl
#else
#define debug(...) {}
#endif

template<class T> auto& operator<<(ostream &o, const vector<T> & v);
template<class T> auto& operator<<(ostream &o, const set<T> & v);
template<class A, class B> auto& operator<<(ostream &o, const pair<A, B> & p);

template<class T> auto& operator<<(ostream &o, const vector<T> & v) {
	cout << "[ "; for (const auto & x: v) cout << x << " "; cout << "]";
	return o;
}
template<class T> auto& operator<<(ostream &o, const set<T> & v) {
	cout << "{ "; for (const auto & x: v) cout << x << " "; cout << "}";
	return o;
}
template<class A, class B> auto& operator<<(ostream &o, const pair<A, B> & p) {
	cout << "(" << p.first << " " << p.second << ")";
	return o;
}

template<class T> inline void chmin(T & a, const T b){ if (a > b) a = b; }
template<class T> inline void chmax(T & a, const T b){ if (a < b) a = b; }

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

const ll oo = 0x3f3f3f3f3f3f3f3f;

template<class T = int>
struct Bit2D {
    vector<T> ord;
    vector<vector<T>> fw, coord;

    Bit2D(vector<pair<T, T>> pts) {
		sort(all(pts));
        for(auto a : pts) {
            if(ord.empty() || a.first != ord.back()) {
                ord.push_back(a.first);
            }
        }
        fw.resize(ord.size() + 1);
        coord.resize(fw.size());
        for(auto &a : pts) {
            swap(a.first, a.second);
        }
        sort(all(pts));
        for(auto &a : pts) {
            swap(a.first, a.second);
            for(int on = upper_bound(ord.begin(), ord.end(), a.first) - ord.begin(); on < fw.size(); on += on & -on) {
                if(coord[on].empty() || coord[on].back() != a.second) {
                    coord[on].push_back(a.second);
                }
            }
        }
        for(int i = 0; i < fw.size(); i++) {
            fw[i].assign(coord[i].size() + 1, 0);
        }
    }

    void upd(T x, T y, T v) {
        for(int xx = upper_bound(ord.begin(), ord.end(), x) - ord.begin(); xx < fw.size(); xx += xx & -xx) {
            for(int yy = upper_bound(coord[xx].begin(), coord[xx].end(), y) - coord[xx].begin(); yy < fw[xx].size(); yy += yy & -yy) {
                fw[xx][yy] += v;
            }
        }
    }

    T qry(T x, T y) {
        T ans = 0;
        for(int xx = upper_bound(ord.begin(), ord.end(), x) - ord.begin(); xx > 0; xx -= xx & -xx) {
            for(int yy = upper_bound(coord[xx].begin(), coord[xx].end(), y) - coord[xx].begin(); yy > 0; yy -= yy & -yy) {
                ans += fw[xx][yy];
            }
        }
        return ans;
    }

    T qry(T x1, T y1, T x2, T y2) {
        return qry(x2, y2) - qry(x2, y1 - 1) - qry(x1 - 1, y2) + qry(x1 - 1, y1 - 1);
    }

    void upd(T x1, T y1, T x2, T y2, T v) {
        upd(x1, y1, v);
        upd(x1, y2 + 1, -v);
        upd(x2 + 1, y1, -v);
        upd(x2 + 1, y2 + 1, v);
    }
};

struct Info {
	int l, r, lt, rt;
};

auto& operator<<(ostream &o, const Info & p) {
	cout << "(" << p.l << " " << p.r << " " << p.lt << " " << p.rt << ")";
	return o;
}

void solve() {
	int n, q;
	cin >> n >> q;
	string s; cin >> s;
	set<pair<pair<int, int>, int>> inter;
	rep(i, 0, n) {
		if (s[i] == '0') continue;
		int j = i;
		while(j < n && s[i] == s[j]) j++;
		inter.insert({{i, j-1}, 0});
		i = j-1;
	}
	vector<Info> caras;

	auto add = [&](int l, int r, int t, int idx) {
		auto it = inter.upper_bound({{r+1 + 1, -1}, -1});
		vector<pair<pair<int, int>, int>> cs;
		while(it != inter.begin()) {
			it--;
			auto [lx, rx] = it->first;
			if (rx+1 < l) break;
			else cs.pb(*it);
		}
		vector<pair<int, int>> to_add;
		for (auto c: cs) {
			inter.erase(c);
			auto [lx, rx] = c.first;
			caras.pb({lx, rx, c.second, t-1});

			if (s[idx] == '1') {
				l = min(l, lx);
				r = max(r, rx);
			}
			else {
				to_add.pb({lx, l-1});
				to_add.pb({r+1, rx});
			}
		}
		if (s[idx] == '1') {
			to_add.pb({l, r});
		}
		for (auto [lx, rx]: to_add) {
			if (lx <= rx) inter.insert({{lx, rx}, t});
		}
	};

	rep(i, 0, q) {
		string act; cin >> act;
		if (act == "query") {
			int a, b;
			cin >> a >> b;
			a--; b--;
			caras.pb({a, b-1, -1, i+1});
		} 
		else if (act == "toggle") {
			int idx; cin >> idx;
			idx--;
			s[idx] = (s[idx] == '1' ? '0' : '1');
			add(idx, idx, i +1, idx);
		}
		else assert(0);
	}
	for (auto c: inter) {
		auto [lx, rx] = c.first;
		caras.pb({lx, rx, c.second, q+1});
	}

	// debug(caras);

	// inter open before query, inter close does not matter, so query is close
	vector<tuple<int, int, int>> sweep;

	rep(i, 0, sz(caras)) {
		auto c = caras[i];
		if (c.lt == -1) {
			sweep.eb(c.rt, 1, i);
		}
		else {
			sweep.eb(c.lt, 0, i);
			sweep.eb(c.rt, 2, i);
		}
	}
	sort(all(sweep));

	vector<pair<ll, ll>> pts;
	auto query_pts = [&](int x1, int y1, int x2, int y2) {
        pts.eb(x2, y2); pts.eb(x2, y1 - 1); pts.eb(x1 - 1, y2); pts.eb(x1 - 1, y1 - 1);
	};
	auto update_pts = [&](int x1, int y1) {
        pts.eb(x1, y1);
	};
	// Finding pts;
	{
		for (auto [_, t, idx]: sweep) {
			auto c = caras[idx];
			if (c.lt == -1) { // query
				query_pts(0, c.r, c.l, n+1);
			}
			else {
				update_pts(c.l, c.r);
			}
		}
	}

	vector<int> ans(q, -1);
	Bit2D<ll> bit1(pts), bitl(pts);
	for (auto [_, t, idx]: sweep) {
		auto c = caras[idx];
		// debug(c);
		if (t == 0)  {
			bit1.upd(c.l, c.r, 1);
			bitl.upd(c.l, c.r, -(c.lt));
		}
		else if (t == 1) { // query
			ll res = (ll)c.rt * bit1.qry(0, c.r, c.l, n) + bitl.qry(0, c.r, c.l, n);
			ans[c.rt-1] = res;
		}
		else if (t == 2) {
			bit1.upd(c.l, c.r, -1);
			bitl.upd(c.l, c.r, -(-(c.lt)));

			bitl.upd(c.l, c.r, c.rt - c.lt + 1);
		}
	}

	for (auto x: ans) {
		if (x != -1) cout << x << endl;
	}
}

int32_t main() {
	#ifndef INTERACTIVE
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#endif

	int t = 1;
	// cin >> t;
	for (int i = 0; i < t; i++) {
		solve();
	}
	return 0;
}

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