Submission #254632

#	Time	Username	Problem	Language	Result	Execution time	Memory
254632		Mahdi_Jfri	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3028 ms	63828 KiB

street_lamps

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

#define ll long long
#define pb push_back
#define lb(a) ((a)&(-(a)))

const int maxn = 3e5 + 20;
const int maxb = 20;

string s , type[maxn];

int l[maxn] , r[maxn] , ind[maxn] , pos[maxn] , where[maxn];

int seg[maxb][maxn] , nq , fen[maxb][maxn];

bool cmp(int x , int y)
{
	return l[x] < l[y];
}

void addFen(int p , int val , int h)
{
	for(p += 5; p < maxn; p += lb(p))
		fen[h][p] += val;
}

int getFen(int p , int h)
{
	int res = 0;
	for(p += 5; p > 0; p -= lb(p))
		res += fen[h][p];

	return res;
}

void build(int s = 0 , int e = nq , int v = 1 , int h = 0)
{
	if(e - s < 2)
	{
		seg[h][s] = r[ind[s]];
		return;
	}

	int m = (s + e) / 2;
	build(s , m , 2 * v , h + 1);
	build(m , e , 2 * v + 1 , h + 1);

	merge(seg[h + 1] + s , seg[h + 1] + m , seg[h + 1] + m , seg[h + 1] + e , seg[h] + s);
}

void add(int l , int r , int lx , int rx , int val , int s = 0 , int e = nq , int v = 1 , int h = 0)
{
	if(l <= s && e <= r)
	{
		int L = lower_bound(seg[h] + s , seg[h] + e , lx) - seg[h];
		int R = lower_bound(seg[h] + s , seg[h] + e , rx) - seg[h];

		addFen(L , val , h);
		addFen(R , -val , h);

		return;
	}
	if(r <= s || e <= l)
		return;

	int m = (s + e) / 2;
	add(l , r , lx , rx , val , s , m , 2 * v , h + 1);
	add(l , r , lx , rx , val , m , e , 2 * v + 1 , h + 1);
}

int get(int p , int r , int s = 0 , int e = nq , int v = 1 , int h = 0)
{
	int x = lower_bound(seg[h] + s , seg[h] + e , r) - seg[h];
	int res = getFen(x , h);

	if(e - s < 2)
		return res;

	int m = (s + e) / 2;

	if(p < m)
		return res + get(p , r , s , m , 2 * v , h + 1);
	else
		return res + get(p , r , m , e , 2 * v + 1 , h + 1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n , q;
	cin >> n >> q;

	cin >> s;

	for(int i = 0; i < q; i++)
	{
		cin >> type[i];
		if(type[i] == "toggle")
		{
			cin >> pos[i];
			pos[i]--;
		}
		else
		{
			cin >> l[i] >> r[i];
			l[i]--;
			r[i]--;
			ind[nq++] = i;
		}
	}

	sort(ind , ind + nq , cmp);
	for(int i = 0; i < nq; i++)
		where[ind[i]] = i;

	build();

	set<int> st;
	st.insert(-1);
	st.insert(n);

	addFen(0 , q , 0);

	for(int i = 0; i < n; i++)
		if(s[i] == '0')
		{
			st.insert(i);
			auto it = st.lower_bound(i);
			it--;
			int l0 = *it + 1, r0 = *st.upper_bound(i);

			l[q] = l0; int L = lower_bound(ind , ind + nq , q , cmp) - ind;
			l[q] = i; int R = upper_bound(ind , ind + nq , q , cmp) - ind;
			add(L , R , i + 1 , r0 + 1 , -q);
		}

	for(int i = 0; i < q; i++)
	{
		if(type[i] == "toggle")
		{
			auto it = st.lower_bound(pos[i]);
			it--;
			int l0 = *it + 1, r0 = *st.upper_bound(pos[i]);

			l[q] = l0; int L = lower_bound(ind , ind + nq , q , cmp) - ind;
			l[q] = pos[i]; int R = upper_bound(ind , ind + nq , q , cmp) - ind;
			if(s[pos[i]] == '0')
				add(L , R , pos[i] + 1 , r0 + 1 , q - i - 1) , s[pos[i]] = '1' , st.erase(pos[i]);
			else
				add(L , R , pos[i] + 1 , r0 + 1 , -(q - i - 1)) , s[pos[i]] = '0' , st.insert(pos[i]);
		}
		else
		{
			bool is = 1;
			auto it = st.lower_bound(l[i]);
			if(it != st.end() && *it < r[i])
				is = 0;
			cout << get(where[i] , r[i]) - (is? q - i - 1 : 0) << endl; 
		}
	}
}

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