Submission #556509

#	Time	Username	Problem	Language	Result	Execution time	Memory
556509		vovamr	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	5041 ms	13908 KiB

street_lamps

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

struct node {
	node *l = nullptr;
	node *r = nullptr;
	ll s = 0;
	node() {}
	node(ll x) : s(x) {}
};
inline void upd1(node *&v, int vl, int vr, int pos, ll x) {
	if (!v) v = new node();
	if (vl == vr) return void(v->s += x);
	int m = vl + vr >> 1;
	if (pos <= m) upd1(v->l, vl, m, pos, x);
	else upd1(v->r, m + 1, vr, pos, x);
	v->s = 0;
	if (v->l) v->s += v->l->s;
	if (v->r) v->s += v->r->s;
}
inline ll get1(node *v, int vl, int vr, int l, int r) {
	if (!v || l > r) return 0;
	else if (vl == l && vr == r) return v->s;
	int m = vl + vr >> 1;
	ll a = get1(v->l, vl, m, l, min(r, m));
	ll b = get1(v->r, m + 1, vr, max(l, m + 1), r);
	return a + b;
}

const int N = 1e5 + 5;
const int L = 0, R = 1e5 + 5;
struct seg2d {
	node *t[4 * N]; int n;
	inline ll get(int v, int vl, int vr, int lx, int rx, int ly, int ry) {
		if (lx > rx || !t[v]) return 0;
		else if (vl == lx && vr == rx) return get1(t[v], L, R, ly, ry);
		int m = vl + vr >> 1;
		ll a = get(2 * v + 1, vl, m, lx, min(rx, m), ly, ry);
		ll b = get(2 * v + 2, m + 1, vr, max(lx, m + 1), rx, ly, ry);
		return a + b;
	}
	inline void upd(int v, int vl, int vr, int x, int y, ll d) {
		upd1(t[v], L, R, y, d);
		if (vl == vr) return;
		int m = vl + vr >> 1;
		if (x <= m) upd(2 * v + 1, vl, m, x, y, d);
		else upd(2 * v + 2, m + 1, vr, x, y, d);
	}

	seg2d(int n = 0) : n(n) {}
	inline ll get(int lx, int rx, int ly, int ry) {
		return get(0, 0, n, lx, rx, ly, ry);
	}
	inline void upd(int x, int y, ll d) {
		upd(0, 0, n, x, y, d);
	}
};

inline void solve() {
	int n, q;
	cin >> n >> q;
	string s; cin >> s;

	map<int,array<int,3>> mp; int ls = -1;
	for (int i = n - 1; ~i; --i) {
		if (s[i] == '1' && ls == -1) ls = i;
		else if (s[i] == '0') {
			if (i + 1 < n && s[i + 1] == '1') {
				mp[i + 1] = {ls, 0, iinf};
			} ls = -1;
		}
	}
	if (s[0] == '1') mp[0] = {ls, 0, iinf};

	seg2d cnt(n + 10);
	seg2d left(n + 10);
	seg2d right(n + 10);

	set<array<int,4>> st;

	auto add_seg = [&](int lt, int rt, int l, int r) {
		st.insert({lt, rt, l, r});

		left.upd(l, r, -lt);
		if (rt == iinf) cnt.upd(l, r, +1);
		else right.upd(l, r, +rt);
	};
	auto del_seg = [&](int lt, int rt, int l, int r) {
		st.erase({lt, rt, l, r});

		left.upd(l, r, lt);
		if (rt == iinf) cnt.upd(l, r, -1);
		else right.upd(l, r, -rt);
	};

	for (auto &[l, __] : mp) {
		auto &[r, lt, rt] = __;
		add_seg(lt, rt, l, r);
	}

	auto upd = [&](int pos, int curtime) {
		if (s[pos] == '0') {
			pii add = {pos, pos};
			auto it = mp.upper_bound(pos);
			if (it != mp.end()) {
				auto [r, lt, rt] = it->se;
				if (it->fi == pos + 1) {
					add = {add.fi, r};
					del_seg(lt, rt, it->fi, r);
					add_seg(lt, curtime - 1, it->fi, r);
					mp.erase(it);
				}
			}
			it = mp.upper_bound(pos);
			if (it != mp.begin()) {
				--it;
				auto [r, lt, rt] = it->se;
				if (r == pos - 1) {
					add = {it->fi, add.se};
					del_seg(lt, rt, it->fi, r);
					add_seg(lt, curtime - 1, it->fi, r);
					mp.erase(it);
				}
			}
			add_seg(curtime, iinf, add.fi, add.se);
			mp[add.fi] = {add.se, curtime, iinf};
		}
		else {
			auto it = mp.upper_bound(pos); --it;
			int l = it->fi; auto [r, lt, rt] = it->se;

			del_seg(lt, rt, l, r);
			add_seg(lt, curtime - 1, l, r);
			mp.erase(it);

			if (l != r) {
				if (pos == l) add_seg(curtime, iinf, l + 1, r), mp[l + 1] = {r, curtime, iinf};
				else if (pos == r) add_seg(curtime, iinf, l, r - 1), mp[l] = {r - 1, curtime, iinf};
				else {
					add_seg(curtime, iinf, l, pos - 1);
					add_seg(curtime, iinf, pos + 1, r);
					mp[l] = {pos - 1, curtime, iinf};
					mp[pos + 1] = {r, curtime, iinf};
				}
			}
		}
		s[pos] = (s[pos] == '0' ? '1' : '0');
	};

	int tm = 0;
	while (q--) { ++tm;
		string e; cin >> e;
		if (e == "toggle") {
			int pos;
			cin >> pos;
			upd(--pos, tm);

//			cout << "s: " << s << '\n';			
//			for (auto &[l, _] : mp) cout << l + 1 << " " << _[0] + 1 << '\n';
//			cout << '\n' << '\n';
		}
		else {
			int l, r;
			cin >> l >> r, --l, ----r;
			
			int ans = 0;
			for (auto &[lt, rt, L, R] : st) {
				if (L <= l && R >= r) {
					ans += min(tm, rt) - lt;
				}
			} cout << ans << '\n';

/**
			int ans = 0;
			ans += right.get(0, l, r, n + 10);
			ans += left.get(0, l, r, n + 10);
			ans += tm * cnt.get(0, l, r, n + 10);
			cout << ans << '\n';
*/
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
/**
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 5
query 1 6
*/

Compilation message (stderr)

street_lamps.cpp: In function 'void upd1(node*&, int, int, int, long long int)':
street_lamps.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |  int m = vl + vr >> 1;
      |          ~~~^~~~
street_lamps.cpp: In function 'long long int get1(node*, int, int, int, int)':
street_lamps.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |  int m = vl + vr >> 1;
      |          ~~~^~~~
street_lamps.cpp: In member function 'long long int seg2d::get(int, int, int, int, int, int, int)':
street_lamps.cpp:56:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   int m = vl + vr >> 1;
      |           ~~~^~~~
street_lamps.cpp: In member function 'void seg2d::upd(int, int, int, int, int, long long int)':
street_lamps.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   int m = vl + vr >> 1;
      |           ~~~^~~~

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