Submission #167615

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167615	2019-12-09T06:08:17 Z	qkxwsm	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3344 ms	402880 KB

street_lamps

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

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;
}

struct custom_hash
{
	template<class T>
	unsigned long long operator()(T v) const
	{
		unsigned long long x = v;
		x = (x ^ (x >> 27)) * 10723151780598845931ull;
		return x ^ (x >> 31);
	}
};

template<class T, class U> using hash_table = gp_hash_table<T, U>;

#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];
hash_table<int, ll> fen[MAXN];
int lst[MAXN];
set<int> lts, rts;
int ans;

void upd(int x, int y, int val)
{
	for (int e = x + 1; e <= N; e += e & (-e))
	{
		for (int f = y + 1; f <= N; f += f & (-f))
		{
			fen[e][f] += val;
		}
	}
}
ll qry(int x, int y)
{
	ll res = 0;
	for (int e = x + 1; e; e -= e & (-e))
	{
		for (int f = y + 1; f; f -= f & (-f))
		{
			auto it = fen[e].find(f);
			if (it != fen[e].end())
			{
				res += it -> se;
			}
		}
	}
	return res;
}
void del(int idx, int t)
{
	int lt = *prev(lts.UB(idx)), rt = *rts.LB(idx);
	lts.erase(lt); rts.erase(rt);
	upd(lt, N - 1 - rt, t - lst[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)
{
	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);
		upd(lt, N - idx, t - lst[lt]);
		upd(idx + 1, N - 1 - rt, t - lst[idx + 1]);
		lst[lt] = t;
	}
	else if (rts.find(idx - 1) != rts.end())
	{
		int lt = *prev(lts.UB(idx));
		rts.erase(idx - 1);
		rts.insert(idx);
		upd(lt, N - idx, t - lst[lt]);
		lst[lt] = t;
	}
	else if (lts.find(idx + 1) != lts.end())
	{
		int rt = *rts.LB(idx);
		lts.erase(idx + 1);
		lts.insert(idx);
		upd(idx + 1, N - 1 - rt, t - lst[idx + 1]);
		lst[idx] = t;
	}
	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};
		}
	}
	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);
			}
			else
			{
				del(idx, i);
			}
			state[idx] = state[idx] ^ 1;
		}
		else
		{
			int lt = quer[i].fi, rt = quer[i].se;
			ans = qry(lt, N - 1 - rt);
			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

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	107640 KB	Output is correct
2	Correct	126 ms	107640 KB	Output is correct
3	Correct	125 ms	107768 KB	Output is correct
4	Correct	124 ms	107640 KB	Output is correct
5	Correct	124 ms	107640 KB	Output is correct
6	Correct	125 ms	107640 KB	Output is correct
7	Correct	125 ms	107768 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	321 ms	111008 KB	Output is correct
2	Correct	386 ms	111344 KB	Output is correct
3	Correct	645 ms	117028 KB	Output is correct
4	Correct	2877 ms	329840 KB	Output is correct
5	Correct	3004 ms	361032 KB	Output is correct
6	Correct	2734 ms	339736 KB	Output is correct
7	Correct	533 ms	111108 KB	Output is correct
8	Correct	535 ms	112440 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	127 ms	108108 KB	Output is correct
2	Correct	129 ms	108096 KB	Output is correct
3	Correct	128 ms	108108 KB	Output is correct
4	Correct	125 ms	107640 KB	Output is correct
5	Correct	2988 ms	402880 KB	Output is correct
6	Correct	3344 ms	393584 KB	Output is correct
7	Correct	2940 ms	360676 KB	Output is correct
8	Correct	514 ms	113548 KB	Output is correct
9	Correct	221 ms	111276 KB	Output is correct
10	Correct	229 ms	111480 KB	Output is correct
11	Correct	235 ms	111628 KB	Output is correct
12	Correct	491 ms	112140 KB	Output is correct
13	Correct	519 ms	113576 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	107616 KB	Output is correct
2	Correct	126 ms	107896 KB	Output is correct
3	Correct	135 ms	108152 KB	Output is correct
4	Correct	126 ms	108024 KB	Output is correct
5	Correct	1565 ms	131572 KB	Output is correct
6	Correct	2612 ms	258956 KB	Output is correct
7	Correct	2970 ms	340244 KB	Output is correct
8	Correct	3016 ms	369216 KB	Output is correct
9	Correct	388 ms	111452 KB	Output is correct
10	Correct	340 ms	111032 KB	Output is correct
11	Correct	388 ms	111608 KB	Output is correct
12	Correct	338 ms	110920 KB	Output is correct
13	Correct	393 ms	111688 KB	Output is correct
14	Correct	337 ms	110840 KB	Output is correct
15	Correct	518 ms	111376 KB	Output is correct
16	Correct	526 ms	112780 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	107640 KB	Output is correct
2	Correct	126 ms	107640 KB	Output is correct
3	Correct	125 ms	107768 KB	Output is correct
4	Correct	124 ms	107640 KB	Output is correct
5	Correct	124 ms	107640 KB	Output is correct
6	Correct	125 ms	107640 KB	Output is correct
7	Correct	125 ms	107768 KB	Output is correct
8	Correct	321 ms	111008 KB	Output is correct
9	Correct	386 ms	111344 KB	Output is correct
10	Correct	645 ms	117028 KB	Output is correct
11	Correct	2877 ms	329840 KB	Output is correct
12	Correct	3004 ms	361032 KB	Output is correct
13	Correct	2734 ms	339736 KB	Output is correct
14	Correct	533 ms	111108 KB	Output is correct
15	Correct	535 ms	112440 KB	Output is correct
16	Correct	127 ms	108108 KB	Output is correct
17	Correct	129 ms	108096 KB	Output is correct
18	Correct	128 ms	108108 KB	Output is correct
19	Correct	125 ms	107640 KB	Output is correct
20	Correct	2988 ms	402880 KB	Output is correct
21	Correct	3344 ms	393584 KB	Output is correct
22	Correct	2940 ms	360676 KB	Output is correct
23	Correct	514 ms	113548 KB	Output is correct
24	Correct	221 ms	111276 KB	Output is correct
25	Correct	229 ms	111480 KB	Output is correct
26	Correct	235 ms	111628 KB	Output is correct
27	Correct	491 ms	112140 KB	Output is correct
28	Correct	519 ms	113576 KB	Output is correct
29	Correct	125 ms	107616 KB	Output is correct
30	Correct	126 ms	107896 KB	Output is correct
31	Correct	135 ms	108152 KB	Output is correct
32	Correct	126 ms	108024 KB	Output is correct
33	Correct	1565 ms	131572 KB	Output is correct
34	Correct	2612 ms	258956 KB	Output is correct
35	Correct	2970 ms	340244 KB	Output is correct
36	Correct	3016 ms	369216 KB	Output is correct
37	Correct	388 ms	111452 KB	Output is correct
38	Correct	340 ms	111032 KB	Output is correct
39	Correct	388 ms	111608 KB	Output is correct
40	Correct	338 ms	110920 KB	Output is correct
41	Correct	393 ms	111688 KB	Output is correct
42	Correct	337 ms	110840 KB	Output is correct
43	Correct	518 ms	111376 KB	Output is correct
44	Correct	526 ms	112780 KB	Output is correct
45	Correct	207 ms	110488 KB	Output is correct
46	Correct	262 ms	110296 KB	Output is correct
47	Correct	1264 ms	187772 KB	Output is correct
48	Correct	2734 ms	329860 KB	Output is correct
49	Correct	245 ms	111432 KB	Output is correct
50	Correct	246 ms	111348 KB	Output is correct
51	Correct	250 ms	111496 KB	Output is correct
52	Correct	255 ms	111348 KB	Output is correct
53	Correct	252 ms	111336 KB	Output is correct
54	Correct	252 ms	111424 KB	Output is correct