Submission #167740

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167740	2019-12-10T00:48:09 Z	qkxwsm	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3032 ms	403392 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>
	T operator()(T v) const
	{
		v = (v ^ (v >> 30)) * 2696969696969696969ll;
		return (v ^ (v >> 17));
	}
};

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

#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	127 ms	107640 KB	Output is correct
2	Correct	128 ms	107648 KB	Output is correct
3	Correct	128 ms	107532 KB	Output is correct
4	Correct	130 ms	107740 KB	Output is correct
5	Correct	128 ms	107768 KB	Output is correct
6	Correct	129 ms	107640 KB	Output is correct
7	Correct	129 ms	107620 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	330 ms	111608 KB	Output is correct
2	Correct	390 ms	111864 KB	Output is correct
3	Correct	667 ms	117360 KB	Output is correct
4	Correct	2683 ms	331228 KB	Output is correct
5	Correct	2758 ms	362024 KB	Output is correct
6	Correct	2636 ms	340956 KB	Output is correct
7	Correct	565 ms	113264 KB	Output is correct
8	Correct	586 ms	115680 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	131 ms	108240 KB	Output is correct
2	Correct	131 ms	108148 KB	Output is correct
3	Correct	132 ms	108160 KB	Output is correct
4	Correct	129 ms	107640 KB	Output is correct
5	Correct	2948 ms	403392 KB	Output is correct
6	Correct	2935 ms	395264 KB	Output is correct
7	Correct	2751 ms	363232 KB	Output is correct
8	Correct	570 ms	114568 KB	Output is correct
9	Correct	229 ms	112376 KB	Output is correct
10	Correct	232 ms	112632 KB	Output is correct
11	Correct	240 ms	112632 KB	Output is correct
12	Correct	594 ms	113288 KB	Output is correct
13	Correct	695 ms	114700 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	107640 KB	Output is correct
2	Correct	148 ms	107840 KB	Output is correct
3	Correct	135 ms	108012 KB	Output is correct
4	Correct	131 ms	108024 KB	Output is correct
5	Correct	1332 ms	133400 KB	Output is correct
6	Correct	2856 ms	261448 KB	Output is correct
7	Correct	2619 ms	342788 KB	Output is correct
8	Correct	3032 ms	370344 KB	Output is correct
9	Correct	389 ms	112696 KB	Output is correct
10	Correct	343 ms	112020 KB	Output is correct
11	Correct	391 ms	112652 KB	Output is correct
12	Correct	345 ms	112248 KB	Output is correct
13	Correct	395 ms	112632 KB	Output is correct
14	Correct	364 ms	112116 KB	Output is correct
15	Correct	566 ms	112776 KB	Output is correct
16	Correct	643 ms	114116 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	127 ms	107640 KB	Output is correct
2	Correct	128 ms	107648 KB	Output is correct
3	Correct	128 ms	107532 KB	Output is correct
4	Correct	130 ms	107740 KB	Output is correct
5	Correct	128 ms	107768 KB	Output is correct
6	Correct	129 ms	107640 KB	Output is correct
7	Correct	129 ms	107620 KB	Output is correct
8	Correct	330 ms	111608 KB	Output is correct
9	Correct	390 ms	111864 KB	Output is correct
10	Correct	667 ms	117360 KB	Output is correct
11	Correct	2683 ms	331228 KB	Output is correct
12	Correct	2758 ms	362024 KB	Output is correct
13	Correct	2636 ms	340956 KB	Output is correct
14	Correct	565 ms	113264 KB	Output is correct
15	Correct	586 ms	115680 KB	Output is correct
16	Correct	131 ms	108240 KB	Output is correct
17	Correct	131 ms	108148 KB	Output is correct
18	Correct	132 ms	108160 KB	Output is correct
19	Correct	129 ms	107640 KB	Output is correct
20	Correct	2948 ms	403392 KB	Output is correct
21	Correct	2935 ms	395264 KB	Output is correct
22	Correct	2751 ms	363232 KB	Output is correct
23	Correct	570 ms	114568 KB	Output is correct
24	Correct	229 ms	112376 KB	Output is correct
25	Correct	232 ms	112632 KB	Output is correct
26	Correct	240 ms	112632 KB	Output is correct
27	Correct	594 ms	113288 KB	Output is correct
28	Correct	695 ms	114700 KB	Output is correct
29	Correct	145 ms	107640 KB	Output is correct
30	Correct	148 ms	107840 KB	Output is correct
31	Correct	135 ms	108012 KB	Output is correct
32	Correct	131 ms	108024 KB	Output is correct
33	Correct	1332 ms	133400 KB	Output is correct
34	Correct	2856 ms	261448 KB	Output is correct
35	Correct	2619 ms	342788 KB	Output is correct
36	Correct	3032 ms	370344 KB	Output is correct
37	Correct	389 ms	112696 KB	Output is correct
38	Correct	343 ms	112020 KB	Output is correct
39	Correct	391 ms	112652 KB	Output is correct
40	Correct	345 ms	112248 KB	Output is correct
41	Correct	395 ms	112632 KB	Output is correct
42	Correct	364 ms	112116 KB	Output is correct
43	Correct	566 ms	112776 KB	Output is correct
44	Correct	643 ms	114116 KB	Output is correct
45	Correct	214 ms	111456 KB	Output is correct
46	Correct	288 ms	111352 KB	Output is correct
47	Correct	1170 ms	188748 KB	Output is correct
48	Correct	2951 ms	331464 KB	Output is correct
49	Correct	251 ms	112560 KB	Output is correct
50	Correct	266 ms	112504 KB	Output is correct
51	Correct	255 ms	112504 KB	Output is correct
52	Correct	263 ms	112596 KB	Output is correct
53	Correct	255 ms	112572 KB	Output is correct
54	Correct	258 ms	112504 KB	Output is correct