Submission #167611

#	Time	Username	Problem	Language	Result	Execution time	Memory
167611		qkxwsm	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	3335 ms	163260 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define y1 orz
#define y2 tmw
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define MAXN 351313
#define INF 1000000007

#define int long long

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, Q;
bitset<MAXN> state;
pii quer[MAXN];
vi pts[MAXN];
vi ptseg[3 * MAXN], fen[3 * MAXN];
int lst[MAXN];
set<int> lts, rts;
int ans;
int seg[3 * MAXN];

void build(int w, int L, int R)
{
	if (L == R)
	{
		swap(ptseg[w], pts[L]);
		sort(ALL(ptseg[w]));
		ptseg[w].erase(unique(ALL(ptseg[w])), ptseg[w].end());
		fen[w].resize(SZ(ptseg[w]) + 2);
		return;
	}
	int mid = (L + R) >> 1;
	build(w << 1, L, mid);
	build(w << 1 | 1, mid + 1, R);
	int iter = 0;
	FOR(i, 0, SZ(ptseg[w << 1]))
	{
		while(iter < SZ(ptseg[w << 1 | 1]) && ptseg[w << 1 | 1][iter] <= ptseg[w << 1][i])
		{
			if (ptseg[w << 1 | 1][iter] != ptseg[w << 1][i])
			{
				ptseg[w].PB(ptseg[w << 1 | 1][iter]);
			}
			iter++;
		}
		ptseg[w].PB(ptseg[w << 1][i]);
	}
	while(iter < SZ(ptseg[w << 1 | 1]))
	{
		ptseg[w].PB(ptseg[w << 1 | 1][iter]);
		iter++;
	}
	fen[w].resize(SZ(ptseg[w]) + 2);
	return;
}
void upd(int w, int L, int R, int a, int x, int v)
{
	// if (w == 1)
	// {
	// 	cerr << "UPDATE " << a << ',' << x << "with " << v << endl;
	// }
	int idx = LB(ALL(ptseg[w]), x) - ptseg[w].begin();
	assert(ptseg[w][idx] == x);
	for (int e = idx + 1; e < SZ(fen[w]); e += e & (-e))
	{
		fen[w][e] += v;
	}
	if (L == R) return;
	int mid = (L + R) >> 1;
	if (a <= mid) upd(w << 1, L, mid, a, x, v);
	else upd(w << 1 | 1, mid + 1, R, a, x, v);
}
int qry(int w, int L, int R, int a, int b, int y)
{
	// if (w == 1)
	// {
	// 	cerr << "QUERY " << a << ' ' << b << ' ' << y1 << ' ' << y2 << endl;
	// }
	int res = 0;
	if (a <= L && R <= b)
	{
		int idx = UB(ALL(ptseg[w]), y) - ptseg[w].begin() - 1;
		for (int e = idx + 1; e; e -= e & (-e))
		{
			res += fen[w][e];
		}
		return res;
	}
	int mid = (L + R) >> 1;
	if (a <= mid) res += qry(w << 1, L, mid, a, b, y);
	if (mid < b) res += qry(w << 1 | 1, mid + 1, R, a, b, y);
	return res;
}

void del(int idx, int t, bool flag)
{
	int lt = *prev(lts.UB(idx)), rt = *rts.LB(idx);
	lts.erase(lt); rts.erase(rt);
	if (flag)
	{
		upd(1, 0, N - 1, rt, lt, t - lst[lt]);
	}
	else
	{
		pts[rt].PB(lt);
	}
	if (lt != idx)
	{
		lst[lt] = t;
		lts.insert(lt);
		rts.insert(idx - 1);
	}
	if (rt != idx)
	{
		lst[idx + 1] = t;
		lts.insert(idx + 1);
		rts.insert(rt);
	}
}
void ins(int idx, int t, bool flag)
{
	if (rts.find(idx - 1) != rts.end() && lts.find(idx + 1) != lts.end())
	{
		int lt = *prev(lts.UB(idx)), rt = *rts.LB(idx);
		rts.erase(idx - 1);
		lts.erase(idx + 1);
		if (flag)
		{
			upd(1, 0, N - 1, idx - 1, lt, t - lst[lt]);
			upd(1, 0, N - 1, rt, idx + 1, t - lst[idx + 1]);
			lst[lt] = t;
		}
		else
		{
			pts[idx - 1].PB(lt);
			pts[rt].PB(idx + 1);
		}
	}
	else if (rts.find(idx - 1) != rts.end())
	{
		int lt = *prev(lts.UB(idx));
		rts.erase(idx - 1);
		rts.insert(idx);
		if (flag)
		{
			upd(1, 0, N - 1, idx - 1, lt, t - lst[lt]);
			lst[lt] = t;
		}
		else
		{
			pts[idx - 1].PB(lt);
		}
	}
	else if (lts.find(idx + 1) != lts.end())
	{
		int rt = *rts.LB(idx);
		lts.erase(idx + 1);
		lts.insert(idx);
		if (flag)
		{
			upd(1, 0, N - 1, rt, idx + 1, t - lst[idx + 1]);
			//update(idx + 1, rt) with t - ls.
			lst[idx] = t;
		}
		else
		{
			pts[rt].PB(idx + 1);
		}
	}
	else
	{
		lts.insert(idx);
		rts.insert(idx);
		lst[idx] = t;
	}
}

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cout << fixed << setprecision(12);
	cerr << fixed << setprecision(4);
	cin >> N >> Q;
	string temps; cin >> temps;
	FOR(i, 0, N)
	{
		state[i] = (temps[i] == '1');
	}
	FOR(i, 0, N)
	{
		if (state[i] && (i == 0 || !state[i - 1])) lts.insert(i);
		if (state[i] && (i == N - 1 || !state[i + 1])) rts.insert(i);
	}
	for (auto it = lts.begin(); it != lts.end(); it++)
	{
		lst[*it] = -1;
	}
	FOR(i, 0, Q)
	{
		cin >> temps;
		int x, y;
		if (temps[0] == 't')
		{
			cin >> x; x--;
			quer[i] = {-1, x};
		}
		else
		{
			cin >> x >> y; x--; y -= 2;
			quer[i] = {x, y};
		}
	}
	FOR(i, 0, Q)
	{
		if (quer[i].fi == -1)
		{
			int idx = quer[i].se;
			if (!state[idx])
			{
				ins(idx, i, 0);
			}
			else
			{
				del(idx, i, 0);
			}
			state[idx] = state[idx] ^ 1;
		}
	}
	FOR(i, 0, Q)
	{
		if (quer[i].fi == -1)
		{
			int idx = quer[i].se;
			state[idx] = state[idx] ^ 1;
		}
	}
	build(1, 0, N - 1);
	lts.clear(); rts.clear();
	FOR(i, 0, N)
	{
		if (state[i] && (i == 0 || !state[i - 1])) lts.insert(i);
		if (state[i] && (i == N - 1 || !state[i + 1])) rts.insert(i);
	}
	FOR(i, 0, Q)
	{
		if (quer[i].fi == -1)
		{
			int idx = quer[i].se;
			if (!state[idx])
			{
				ins(idx, i, 1);
			}
			else
			{
				del(idx, i, 1);
			}
			state[idx] = state[idx] ^ 1;
		}
		else
		{
			int lt = quer[i].fi, rt = quer[i].se;
			ans = qry(1, 0, N - 1, rt, N - 1, lt);
			auto it = rts.LB(rt);
			if (it != rts.end())
			{
				auto jt = prev(lts.UB(*it));
				if (*jt <= lt)
				{
					int t = lst[*jt];
					ans += (i - t);
				}
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

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