Submission #167737

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167737	2019-12-10T00:33:54 Z	qkxwsm	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3358 ms	403864 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 >> 27)) * 2696969696969696969ll;
		return v;
	}
};

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	126 ms	107640 KB	Output is correct
2	Correct	126 ms	107640 KB	Output is correct
3	Correct	128 ms	107640 KB	Output is correct
4	Correct	126 ms	107640 KB	Output is correct
5	Correct	126 ms	107768 KB	Output is correct
6	Correct	126 ms	107684 KB	Output is correct
7	Correct	125 ms	107640 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	320 ms	111480 KB	Output is correct
2	Correct	380 ms	111956 KB	Output is correct
3	Correct	644 ms	117448 KB	Output is correct
4	Correct	2827 ms	334856 KB	Output is correct
5	Correct	2951 ms	366144 KB	Output is correct
6	Correct	2753 ms	344404 KB	Output is correct
7	Correct	684 ms	115340 KB	Output is correct
8	Correct	587 ms	118348 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	132 ms	108300 KB	Output is correct
2	Correct	131 ms	108124 KB	Output is correct
3	Correct	132 ms	108024 KB	Output is correct
4	Correct	128 ms	107656 KB	Output is correct
5	Correct	2909 ms	403864 KB	Output is correct
6	Correct	3247 ms	398204 KB	Output is correct
7	Correct	2862 ms	365800 KB	Output is correct
8	Correct	537 ms	118324 KB	Output is correct
9	Correct	245 ms	113144 KB	Output is correct
10	Correct	231 ms	113700 KB	Output is correct
11	Correct	236 ms	113912 KB	Output is correct
12	Correct	579 ms	116900 KB	Output is correct
13	Correct	539 ms	118412 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	107640 KB	Output is correct
2	Correct	129 ms	107876 KB	Output is correct
3	Correct	139 ms	107976 KB	Output is correct
4	Correct	131 ms	108024 KB	Output is correct
5	Correct	1609 ms	137088 KB	Output is correct
6	Correct	2630 ms	264412 KB	Output is correct
7	Correct	2941 ms	344864 KB	Output is correct
8	Correct	3358 ms	372560 KB	Output is correct
9	Correct	404 ms	114084 KB	Output is correct
10	Correct	340 ms	113272 KB	Output is correct
11	Correct	395 ms	114340 KB	Output is correct
12	Correct	342 ms	113016 KB	Output is correct
13	Correct	391 ms	114168 KB	Output is correct
14	Correct	349 ms	113080 KB	Output is correct
15	Correct	546 ms	117096 KB	Output is correct
16	Correct	542 ms	118540 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	126 ms	107640 KB	Output is correct
2	Correct	126 ms	107640 KB	Output is correct
3	Correct	128 ms	107640 KB	Output is correct
4	Correct	126 ms	107640 KB	Output is correct
5	Correct	126 ms	107768 KB	Output is correct
6	Correct	126 ms	107684 KB	Output is correct
7	Correct	125 ms	107640 KB	Output is correct
8	Correct	320 ms	111480 KB	Output is correct
9	Correct	380 ms	111956 KB	Output is correct
10	Correct	644 ms	117448 KB	Output is correct
11	Correct	2827 ms	334856 KB	Output is correct
12	Correct	2951 ms	366144 KB	Output is correct
13	Correct	2753 ms	344404 KB	Output is correct
14	Correct	684 ms	115340 KB	Output is correct
15	Correct	587 ms	118348 KB	Output is correct
16	Correct	132 ms	108300 KB	Output is correct
17	Correct	131 ms	108124 KB	Output is correct
18	Correct	132 ms	108024 KB	Output is correct
19	Correct	128 ms	107656 KB	Output is correct
20	Correct	2909 ms	403864 KB	Output is correct
21	Correct	3247 ms	398204 KB	Output is correct
22	Correct	2862 ms	365800 KB	Output is correct
23	Correct	537 ms	118324 KB	Output is correct
24	Correct	245 ms	113144 KB	Output is correct
25	Correct	231 ms	113700 KB	Output is correct
26	Correct	236 ms	113912 KB	Output is correct
27	Correct	579 ms	116900 KB	Output is correct
28	Correct	539 ms	118412 KB	Output is correct
29	Correct	129 ms	107640 KB	Output is correct
30	Correct	129 ms	107876 KB	Output is correct
31	Correct	139 ms	107976 KB	Output is correct
32	Correct	131 ms	108024 KB	Output is correct
33	Correct	1609 ms	137088 KB	Output is correct
34	Correct	2630 ms	264412 KB	Output is correct
35	Correct	2941 ms	344864 KB	Output is correct
36	Correct	3358 ms	372560 KB	Output is correct
37	Correct	404 ms	114084 KB	Output is correct
38	Correct	340 ms	113272 KB	Output is correct
39	Correct	395 ms	114340 KB	Output is correct
40	Correct	342 ms	113016 KB	Output is correct
41	Correct	391 ms	114168 KB	Output is correct
42	Correct	349 ms	113080 KB	Output is correct
43	Correct	546 ms	117096 KB	Output is correct
44	Correct	542 ms	118540 KB	Output is correct
45	Correct	209 ms	111596 KB	Output is correct
46	Correct	261 ms	111736 KB	Output is correct
47	Correct	1262 ms	190068 KB	Output is correct
48	Correct	2714 ms	334524 KB	Output is correct
49	Correct	255 ms	114296 KB	Output is correct
50	Correct	251 ms	114040 KB	Output is correct
51	Correct	264 ms	114412 KB	Output is correct
52	Correct	274 ms	114524 KB	Output is correct
53	Correct	263 ms	114552 KB	Output is correct
54	Correct	258 ms	114552 KB	Output is correct