Submission #167559

#	Time	Username	Problem	Language	Result	Execution time	Memory
167559		qkxwsm	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	463 ms	82032 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

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];
map<int, 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]);
		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();
	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 y1, int y2)
{
	if (w == 1)
	{
		//cerr << "QUERY " << a << ' ' << b << ' ' << y1 << ' ' << y2 << endl;
	}
	////cerr << "INSIDE " << L << ' ' << R << endl;
	////cerr << endl;
	if (a <= L && R <= b)
	{
		int res = 0;
		int idx = UB(ALL(ptseg[w]), y2) - ptseg[w].begin() - 1;
		for (int e = idx + 1; e; e -= e & (-e))
		{
			////cerr << "PLUS " << fen[w][e] << endl;
			res += fen[w][e];
		}
		idx = UB(ALL(ptseg[w]), y1 - 1) - ptseg[w].begin() - 1;
		for (int e = idx + 1; e; e -= e & (-e))
		{
			////cerr << "MINUS " << fen[w][e] << endl;
			res -= fen[w][e];
		}
		return res;
	}
	int mid = (L + R) >> 1, res = 0;
	if (a <= mid) res += qry(w << 1, L, mid, a, b, y1, y2);
	else res += qry(w << 1 | 1, mid + 1, R, a, b, y1, y2);
	return res;
}

void update(int w, int L, int R, int a, int t)
{
	if (L == R)
	{
		seg[w] = t;
		return;
	}
	int mid = (L + R) >> 1;
	if (a <= mid)
	{
		update(w << 1, L, mid, a, t);
	}
	else
	{
		update(w << 1 | 1, mid + 1, R, a, t);
	}
	seg[w] = max(seg[w << 1], seg[w << 1 | 1]);
}
int query(int w, int L, int R, int a, int b)
{
	if (a <= L && R <= b)
	{
		return seg[w];
	}
	int mid = (L + R) >> 1, res = -INF;
	if (a <= mid)
	{
		ckmax(res, query(w << 1, L, mid, a, b));
	}
	if (mid < b)
	{
		ckmax(res, query(w << 1 | 1, mid + 1, R, a, b));
	}
	return res;
}
void del(int idx, int t, bool flag)
{
	//cerr << "DEL " << idx << ' ' << t << ' ' << flag << endl;
	int lt = *prev(lts.UB(idx)), rt = *rts.UB(idx);
	lts.erase(lt); rts.erase(rt);
	if (flag)
	{
		//cerr << "FIRST OK TIME " << lst[lt][rt] << endl;
		upd(1, 0, N - 1, lt, rt, t - lst[lt][rt]);
		//update(lt, rt) with t - ls.
	}
	else
	{
		pts[lt].PB(rt);
	}
	if (lt != idx)
	{
		lst[lt][idx - 1] = t;
		lts.insert(lt);
		rts.insert(idx - 1);
	}
	if (rt != idx)
	{
		lst[idx + 1][rt] = t;
		lts.insert(idx + 1);
		rts.insert(rt);
	}
	if (flag)
	{
		update(1, 0, N - 1, idx, Q + 1);
	}
}
void ins(int idx, int t, bool flag)
{
	//cerr << "INS " << idx << ' ' << t << ' ' << flag << endl;
	if (rts.find(idx - 1) != rts.end() && lts.find(idx + 1) != lts.end())
	{
		int lt = *prev(lts.UB(idx)), rt = *rts.UB(idx);
		rts.erase(idx - 1);
		lts.erase(idx + 1);
		if (flag)
		{
			upd(1, 0, N - 1, lt, idx - 1, t - lst[lt][idx - 1]);
			upd(1, 0, N - 1, idx + 1, rt, t - lst[idx + 1][rt]);
			//update(lt, idx - 1) with t - ls
			//update(idx + 1, rt) with t - ls
			lst[lt][rt] = t;
		}
		else
		{
			pts[lt].PB(idx - 1);
			pts[idx + 1].PB(rt);
		}
	}
	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, lt, idx - 1, t - lst[lt][idx - 1]);
			//update(lt, idx - 1) with t - ls.
			lst[lt][idx] = t;
		}
		else
		{
			pts[lt].PB(idx - 1);
		}
	}
	else if (lts.find(idx + 1) != lts.end())
	{
		int rt = *rts.UB(idx);
		lts.erase(idx + 1);
		lts.insert(idx);
		if (flag)
		{
			upd(1, 0, N - 1, idx + 1, rt, t - lst[idx + 1][rt]);
			//update(idx + 1, rt) with t - ls.
			lst[idx][rt] = t;
		}
		else
		{
			pts[idx + 1].PB(rt);
		}
	}
	else
	{
		lts.insert(idx);
		rts.insert(idx);
		lst[idx][idx] = t;
	}
	if (flag)
	{
		update(1, 0, N - 1, 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');
		if (state[i])
		{
			update(1, 0, N - 1, i, -1);
		}
		else
		{
			update(1, 0, N - 1, i, Q + 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(), jt = rts.begin(); it != lts.end(); it++, jt++)
	{
		lst[*it][*jt] = -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;
		}
	}
	FOR(i, 0, N)
	{
		sort(ALL(pts[i]));
		pts[i].erase(unique(ALL(pts[i])), pts[i].end());
		//cerr << "IN PTS " << i << ":";
		for (int x : pts[i])
		{
			//cerr << ' ' << x;
		}
		//cerr << endl;
	}
	build(1, 0, N - 1);
	// ////cerr << "YES\n";
	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);
	}
	// ////cerr << "ALIVE\n";
	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;
			// //////cerr << "ANSWER " << lt << ' ' << rt << endl;
			ans = qry(1, 0, N - 1, 0, lt, rt, N - 1);
			//query rectangle of 0...lt rt....N-1
			int t = query(1, 0, N - 1, lt, rt);
			if (t < i)
			{
				// //cerr << "PEQ " << i - t << endl;
				ans += (i - t);
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:335:12: warning: unused variable 'x' [-Wunused-variable]
   for (int x : pts[i])
            ^

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