Submission #163971

#	Time	Username	Problem	Language	Result	Execution time	Memory
163971		sams	Street Lamps (APIO19_street_lamps)	C++14	40 / 100	334 ms	13580 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5+10;

struct ND
{
	int s, m;	
} seg[4*maxn];

int n, q;
int v[maxn], c[maxn], last[maxn];
string ss;

ND op(ND a, ND b)
{
	return {a.s + b.s, max(a.m, b.m)};
}

void build(int u = 1, int l = 1, int r = n)
{
	if(l == r)
	{
		seg[u] = {v[l], 0};
		return;
	}

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

	build(2*u, l, mid);
	build(2*u + 1, mid + 1, r);

	seg[u] = op(seg[2*u], seg[2*u+1]);
}

ND query(int a, int b, int u = 1, int l = 1 , int r = n)
{
	if(r < a || l > b) return {0, 0};
	if(a <= l && r <= b) return seg[u];

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

	return op(query(a, b, 2*u, l, mid), query(a, b, 2*u+1, mid +1, r));
}

void upd(int a, int t, int u = 1, int l = 1, int r = n)
{
	if(l == r)
	{
		v[l] = (v[l] == 1)? 0 : 1;

		seg[u] = {v[l], t};

		return;
	}

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

	if(a <= mid) upd(a, t, 2*u, l, mid);
	else upd(a, t, 2*u +1, mid +1, r);

	seg[u] = op(seg[2*u], seg[2*u +1]);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> q >> ss;

	for(int i = 0 ; i < n ; ++i)
	{
		if(ss[i] == '0') v[i + 1] = 0;
		else v[i + 1] = 1;
	}

	build();

	for(int i = 1 ; i <= q ; ++i)
	{
		string S;
		int l, r;
		cin >> S >> l;

		if(S == "query")
		{
			cin >> r;

			ND qr = query(l, r-1);
			if(r - l == 1)
			{
				//cout << l << " " << i << " " << c[l] << " " << last[l] << "\n";
				(v[l])? cout << i - c[l] << "\n" : cout << last[l] - c[l] << "\n";
			}
			else
			{
				if(qr.s == r - l) cout << i - qr.m << "\n";
				else cout << "0\n";
			}
		}
		else
		{
			if(v[l] == 1)
			{
				last[l] = i;
			}
			else
			{
				c[l] += i - last[l];
				last[l] = i;
			}
			upd(l, i);
		}
	}
}

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