oj.uz

답안 #167613

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167613 2019-12-09T06:04:49 Z qkxwsm 가로등 (APIO19_street_lamps) C++14
100 / 100
 3229 ms 403276 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, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 107660 KB Output is correct
2 Correct 128 ms 107656 KB Output is correct
3 Correct 127 ms 107628 KB Output is correct
4 Correct 129 ms 107744 KB Output is correct
5 Correct 128 ms 107768 KB Output is correct
6 Correct 127 ms 107596 KB Output is correct
7 Correct 128 ms 107612 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 330 ms 114240 KB Output is correct
2 Correct 385 ms 114928 KB Output is correct
3 Correct 661 ms 121044 KB Output is correct
4 Correct 2829 ms 334804 KB Output is correct
5 Correct 3081 ms 366308 KB Output is correct
6 Correct 2794 ms 344732 KB Output is correct
7 Correct 600 ms 117128 KB Output is correct
8 Correct 631 ms 118540 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 108164 KB Output is correct
2 Correct 131 ms 108060 KB Output is correct
3 Correct 130 ms 108024 KB Output is correct
4 Correct 128 ms 107768 KB Output is correct
5 Correct 3053 ms 403276 KB Output is correct
6 Correct 3140 ms 398040 KB Output is correct
7 Correct 2911 ms 365688 KB Output is correct
8 Correct 606 ms 117028 KB Output is correct
9 Correct 225 ms 113192 KB Output is correct
10 Correct 253 ms 113784 KB Output is correct
11 Correct 238 ms 113912 KB Output is correct
12 Correct 582 ms 115600 KB Output is correct
13 Correct 609 ms 117060 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 107756 KB Output is correct
2 Correct 129 ms 107792 KB Output is correct
3 Correct 130 ms 108004 KB Output is correct
4 Correct 129 ms 108024 KB Output is correct
5 Correct 1401 ms 137128 KB Output is correct
6 Correct 2423 ms 264212 KB Output is correct
7 Correct 2747 ms 344796 KB Output is correct
8 Correct 3229 ms 372772 KB Output is correct
9 Correct 387 ms 114036 KB Output is correct
10 Correct 344 ms 113148 KB Output is correct
11 Correct 387 ms 114064 KB Output is correct
12 Correct 346 ms 113016 KB Output is correct
13 Correct 388 ms 114092 KB Output is correct
14 Correct 343 ms 113016 KB Output is correct
15 Correct 575 ms 117040 KB Output is correct
16 Correct 573 ms 118536 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 107660 KB Output is correct
2 Correct 128 ms 107656 KB Output is correct
3 Correct 127 ms 107628 KB Output is correct
4 Correct 129 ms 107744 KB Output is correct
5 Correct 128 ms 107768 KB Output is correct
6 Correct 127 ms 107596 KB Output is correct
7 Correct 128 ms 107612 KB Output is correct
8 Correct 330 ms 114240 KB Output is correct
9 Correct 385 ms 114928 KB Output is correct
10 Correct 661 ms 121044 KB Output is correct
11 Correct 2829 ms 334804 KB Output is correct
12 Correct 3081 ms 366308 KB Output is correct
13 Correct 2794 ms 344732 KB Output is correct
14 Correct 600 ms 117128 KB Output is correct
15 Correct 631 ms 118540 KB Output is correct
16 Correct 141 ms 108164 KB Output is correct
17 Correct 131 ms 108060 KB Output is correct
18 Correct 130 ms 108024 KB Output is correct
19 Correct 128 ms 107768 KB Output is correct
20 Correct 3053 ms 403276 KB Output is correct
21 Correct 3140 ms 398040 KB Output is correct
22 Correct 2911 ms 365688 KB Output is correct
23 Correct 606 ms 117028 KB Output is correct
24 Correct 225 ms 113192 KB Output is correct
25 Correct 253 ms 113784 KB Output is correct
26 Correct 238 ms 113912 KB Output is correct
27 Correct 582 ms 115600 KB Output is correct
28 Correct 609 ms 117060 KB Output is correct
29 Correct 133 ms 107756 KB Output is correct
30 Correct 129 ms 107792 KB Output is correct
31 Correct 130 ms 108004 KB Output is correct
32 Correct 129 ms 108024 KB Output is correct
33 Correct 1401 ms 137128 KB Output is correct
34 Correct 2423 ms 264212 KB Output is correct
35 Correct 2747 ms 344796 KB Output is correct
36 Correct 3229 ms 372772 KB Output is correct
37 Correct 387 ms 114036 KB Output is correct
38 Correct 344 ms 113148 KB Output is correct
39 Correct 387 ms 114064 KB Output is correct
40 Correct 346 ms 113016 KB Output is correct
41 Correct 388 ms 114092 KB Output is correct
42 Correct 343 ms 113016 KB Output is correct
43 Correct 575 ms 117040 KB Output is correct
44 Correct 573 ms 118536 KB Output is correct
45 Correct 210 ms 111656 KB Output is correct
46 Correct 269 ms 111864 KB Output is correct
47 Correct 1204 ms 190100 KB Output is correct
48 Correct 2615 ms 334656 KB Output is correct
49 Correct 247 ms 114264 KB Output is correct
50 Correct 246 ms 114040 KB Output is correct
51 Correct 257 ms 114424 KB Output is correct
52 Correct 277 ms 114724 KB Output is correct
53 Correct 254 ms 114680 KB Output is correct
54 Correct 257 ms 114552 KB Output is correct