oj.uz

답안 #167615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167615 2019-12-09T06:08:17 Z qkxwsm 가로등 (APIO19_street_lamps) C++14
100 / 100
 3344 ms 402880 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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