Submission #564191

#	Time	Username	Problem	Language	Result	Execution time	Memory
564191		ngpin04	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3282 ms	128656 KiB

street_lamps

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 3e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> posy[N];
vector <int> bit[N];

int op[N];
int l[N];
int r[N];
int a[N];
int n,q;

void fakeupdate(int x, int y) {
	for (; x <= n; x += x & -x) 
		posy[x].push_back(y);
}

void fakeget(int x, int y) {
	for (; x; x -= x & -x)
		posy[x].push_back(y);
}

void fakeupdate(int x, int u, int y, int v) {
	if (x > u || y > v)
		return;
	fakeupdate(x, y), fakeupdate(u + 1, v + 1);
	fakeupdate(x, v + 1), fakeupdate(u + 1, y);
}

void update(int x, int y, int val) {
	// cerr << x << " " << y << " " << val << "\n";
	for (; x <= n; x += x & -x) {
		int s = lower_bound(ALL(posy[x]), y) - posy[x].begin() + 1;
		for (int i = s; i < (int) bit[x].size(); i += i & -i)
			bit[x][i] += val;
	}
}

int get(int x, int y) {
	int res = 0;
	for (; x > 0; x -= x & -x) {
		int s = lower_bound(ALL(posy[x]), y) - posy[x].begin() + 1;
		for (int i = s; i > 0; i -= i & -i)
			res += bit[x][i];
	}
	return res;
}

void update(int x, int u, int y, int v, int val) {
	if (x > u || y > v)
		return;
	// cerr << x << " " << y << " " << u << " " << v << " " << val << "\n";
	update(x, y, val), update(u + 1, v + 1, val);
	update(x, v + 1, -val), update(u + 1, y, -val);
}

void build() {
	set <pair <int, int>> seg;
	for (int i = 1; i <= n; i++) if (a[i]) {
		int j = i;
		while (a[j])
			j++;

		seg.insert(mp(i, j - 1));
		i = j;
	}

	for (pair <int, int> s : seg)
		fakeupdate(s.fi, s.se, s.fi, s.se);

	for (int i = 1; i <= q; i++) {
		if (op[i] == 0) {
			int pos = l[i];
			if (a[pos]) {
				auto cur = *prev(seg.upper_bound(mp(pos, oo)));
				fakeupdate(cur.fi, pos, pos, cur.se);
				seg.erase(cur);
				if (cur.fi < pos)
					seg.insert(mp(cur.fi, pos - 1));
				if (pos < cur.se)
					seg.insert(mp(pos + 1, cur.se));
			} else {	
				auto it = seg.upper_bound(mp(pos, oo));
				auto f = (it == seg.begin()) ? mp(-1, -1) : *(--(it));
				auto g = (it == seg.end()) ? mp(oo, oo) : *it;
				int l = pos, r = pos;
				if (f.se == l - 1)
					l = f.fi;
				if (g.fi == r + 1)
					r = g.se;

				fakeupdate(l, pos, pos, r);
				seg.insert(mp(l, r));
			}

			a[pos] ^= 1;
		} else {
			fakeget(l[i], r[i]);
		}
	}

	for (int i = 1; i <= n; i++) {
		sort(ALL(posy[i]));
		posy[i].resize(unique(ALL(posy[i])) - posy[i].begin());
		bit[i].assign(posy[i].size() + 1, 0);
	}

	for (int i = 1; i <= q; i++) 
		if (op[i] == 0)
			a[l[i]] ^= 1;
}

void solve() {
	set <pair <int, int>> seg;
	for (int i = 1; i <= n; i++) if (a[i]) {
		int j = i;
		while (a[j])
			j++;

		seg.insert(mp(i, j - 1));
		i = j;
	}

	for (pair <int, int> s : seg) 
		update(s.fi, s.se, s.fi, s.se, q);

	for (int i = 1; i <= q; i++) {

		if (op[i] == 0) {
			int pos = l[i];
			if (a[pos]) {
				auto cur = *prev(seg.upper_bound(mp(pos, oo)));

				update(cur.fi, pos, pos, cur.se, -(q - i));
				seg.erase(cur);
				if (cur.fi < pos)
					seg.insert(mp(cur.fi, pos - 1));
				if (pos < cur.se)
					seg.insert(mp(pos + 1, cur.se));
			} else {	
				auto it = seg.upper_bound(mp(pos, oo));
				auto f = (it == seg.begin()) ? mp(-1, -1) : *prev(it);
				auto g = (it == seg.end()) ? mp(oo, oo) : *it;
				int l = pos, r = pos;
				if (f.se == l - 1) {
					seg.erase(f);
					l = f.fi;
				}
				if (g.fi == r + 1) {
					seg.erase(g);
					r = g.se;
				}
				update(l, pos, pos, r, q - i);
				seg.insert(mp(l, r));
			}

			a[pos] ^= 1;
		} else {
			auto it = seg.upper_bound(mp(l[i], oo));
			int ans = get(l[i], r[i]);
			if (it != seg.begin() && (--it)->se >= r[i]) 
				ans -= q - i;

			cout << ans << "\n";
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> q;
	{
		string str; cin >> str;
		for (int i = 1; i <= n; i++)
			a[i] = str[i - 1] - '0';
	}


	for (int i = 1; i <= q; i++) {
		string qr; cin >> qr;
		if (qr == "query") {
			op[i] = 1;
			cin >> l[i] >> r[i];
		} else
			cin >> l[i];
		r[i]--;
	}

	build();
	solve();
	return 0;
}

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