Submission #167738

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167738	2019-12-10T00:35:15 Z	qkxwsm	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3186 ms	403680 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
	{
		return (v ^ (v >> 27)) * 2696969696969696969ll;
	}
};

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	146 ms	107640 KB	Output is correct
2	Correct	139 ms	107664 KB	Output is correct
3	Correct	129 ms	107640 KB	Output is correct
4	Correct	129 ms	107640 KB	Output is correct
5	Correct	128 ms	107640 KB	Output is correct
6	Correct	129 ms	107652 KB	Output is correct
7	Correct	128 ms	107552 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	324 ms	111484 KB	Output is correct
2	Correct	384 ms	111860 KB	Output is correct
3	Correct	657 ms	117588 KB	Output is correct
4	Correct	2980 ms	334820 KB	Output is correct
5	Correct	3171 ms	366436 KB	Output is correct
6	Correct	3072 ms	344796 KB	Output is correct
7	Correct	623 ms	115340 KB	Output is correct
8	Correct	576 ms	115020 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	130 ms	108152 KB	Output is correct
2	Correct	132 ms	108152 KB	Output is correct
3	Correct	133 ms	108024 KB	Output is correct
4	Correct	132 ms	107668 KB	Output is correct
5	Correct	3183 ms	403680 KB	Output is correct
6	Correct	3186 ms	397020 KB	Output is correct
7	Correct	2933 ms	362544 KB	Output is correct
8	Correct	561 ms	113928 KB	Output is correct
9	Correct	225 ms	113372 KB	Output is correct
10	Correct	230 ms	113784 KB	Output is correct
11	Correct	237 ms	113912 KB	Output is correct
12	Correct	520 ms	112368 KB	Output is correct
13	Correct	577 ms	113940 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	142 ms	107844 KB	Output is correct
2	Correct	130 ms	107896 KB	Output is correct
3	Correct	140 ms	108032 KB	Output is correct
4	Correct	150 ms	108020 KB	Output is correct
5	Correct	1740 ms	132592 KB	Output is correct
6	Correct	2609 ms	260784 KB	Output is correct
7	Correct	2734 ms	342600 KB	Output is correct
8	Correct	2956 ms	372088 KB	Output is correct
9	Correct	391 ms	113580 KB	Output is correct
10	Correct	340 ms	113144 KB	Output is correct
11	Correct	392 ms	113596 KB	Output is correct
12	Correct	341 ms	113076 KB	Output is correct
13	Correct	391 ms	113592 KB	Output is correct
14	Correct	342 ms	113016 KB	Output is correct
15	Correct	552 ms	111884 KB	Output is correct
16	Correct	568 ms	113292 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	107640 KB	Output is correct
2	Correct	139 ms	107664 KB	Output is correct
3	Correct	129 ms	107640 KB	Output is correct
4	Correct	129 ms	107640 KB	Output is correct
5	Correct	128 ms	107640 KB	Output is correct
6	Correct	129 ms	107652 KB	Output is correct
7	Correct	128 ms	107552 KB	Output is correct
8	Correct	324 ms	111484 KB	Output is correct
9	Correct	384 ms	111860 KB	Output is correct
10	Correct	657 ms	117588 KB	Output is correct
11	Correct	2980 ms	334820 KB	Output is correct
12	Correct	3171 ms	366436 KB	Output is correct
13	Correct	3072 ms	344796 KB	Output is correct
14	Correct	623 ms	115340 KB	Output is correct
15	Correct	576 ms	115020 KB	Output is correct
16	Correct	130 ms	108152 KB	Output is correct
17	Correct	132 ms	108152 KB	Output is correct
18	Correct	133 ms	108024 KB	Output is correct
19	Correct	132 ms	107668 KB	Output is correct
20	Correct	3183 ms	403680 KB	Output is correct
21	Correct	3186 ms	397020 KB	Output is correct
22	Correct	2933 ms	362544 KB	Output is correct
23	Correct	561 ms	113928 KB	Output is correct
24	Correct	225 ms	113372 KB	Output is correct
25	Correct	230 ms	113784 KB	Output is correct
26	Correct	237 ms	113912 KB	Output is correct
27	Correct	520 ms	112368 KB	Output is correct
28	Correct	577 ms	113940 KB	Output is correct
29	Correct	142 ms	107844 KB	Output is correct
30	Correct	130 ms	107896 KB	Output is correct
31	Correct	140 ms	108032 KB	Output is correct
32	Correct	150 ms	108020 KB	Output is correct
33	Correct	1740 ms	132592 KB	Output is correct
34	Correct	2609 ms	260784 KB	Output is correct
35	Correct	2734 ms	342600 KB	Output is correct
36	Correct	2956 ms	372088 KB	Output is correct
37	Correct	391 ms	113580 KB	Output is correct
38	Correct	340 ms	113144 KB	Output is correct
39	Correct	392 ms	113596 KB	Output is correct
40	Correct	341 ms	113076 KB	Output is correct
41	Correct	391 ms	113592 KB	Output is correct
42	Correct	342 ms	113016 KB	Output is correct
43	Correct	552 ms	111884 KB	Output is correct
44	Correct	568 ms	113292 KB	Output is correct
45	Correct	209 ms	111736 KB	Output is correct
46	Correct	266 ms	111780 KB	Output is correct
47	Correct	1267 ms	189928 KB	Output is correct
48	Correct	2680 ms	330216 KB	Output is correct
49	Correct	251 ms	113528 KB	Output is correct
50	Correct	253 ms	113528 KB	Output is correct
51	Correct	254 ms	113656 KB	Output is correct
52	Correct	261 ms	113656 KB	Output is correct
53	Correct	258 ms	113528 KB	Output is correct
54	Correct	258 ms	113600 KB	Output is correct