oj.uz

답안 #167610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167610 2019-12-09T05:54:32 Z qkxwsm 가로등 (APIO19_street_lamps) C++14
20 / 100
 2971 ms 130652 KB 
#include <bits/stdc++.h>

using namespace std;

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;
}

#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];
vi pts[MAXN];
vi ptseg[3 * MAXN], fen[3 * MAXN];
int lst[MAXN];
set<int> lts, rts;
int ans;
int seg[3 * MAXN];

void build(int w, int L, int R)
{
	if (L == R)
	{
		swap(ptseg[w], pts[L]);
		sort(ALL(ptseg[w]));
		ptseg[w].erase(unique(ALL(ptseg[w])), ptseg[w].end());
		fen[w].resize(SZ(ptseg[w]) + 2);
		return;
	}
	int mid = (L + R) >> 1;
	build(w << 1, L, mid);
	build(w << 1 | 1, mid + 1, R);
	int iter = 0;
	FOR(i, 0, SZ(ptseg[w << 1]))
	{
		while(iter < SZ(ptseg[w << 1 | 1]) && ptseg[w << 1 | 1][iter] <= ptseg[w << 1][i])
		{
			if (ptseg[w << 1 | 1][iter] != ptseg[w << 1][i])
			{
				ptseg[w].PB(ptseg[w << 1 | 1][iter]);
			}
			iter++;
		}
		ptseg[w].PB(ptseg[w << 1][i]);
	}
	while(iter < SZ(ptseg[w << 1 | 1]))
	{
		ptseg[w].PB(ptseg[w << 1 | 1][iter]);
		iter++;
	}
	fen[w].resize(SZ(ptseg[w]) + 2);
	return;
}
void upd(int w, int L, int R, int a, int x, int v)
{
	// if (w == 1)
	// {
	// 	cerr << "UPDATE " << a << ',' << x << "with " << v << endl;
	// }
	int idx = LB(ALL(ptseg[w]), x) - ptseg[w].begin();
	assert(ptseg[w][idx] == x);
	for (int e = idx + 1; e < SZ(fen[w]); e += e & (-e))
	{
		fen[w][e] += v;
	}
	if (L == R) return;
	int mid = (L + R) >> 1;
	if (a <= mid) upd(w << 1, L, mid, a, x, v);
	else upd(w << 1 | 1, mid + 1, R, a, x, v);
}
int qry(int w, int L, int R, int a, int b, int y)
{
	// if (w == 1)
	// {
	// 	cerr << "QUERY " << a << ' ' << b << ' ' << y1 << ' ' << y2 << endl;
	// }
	int res = 0;
	if (a <= L && R <= b)
	{
		int idx = UB(ALL(ptseg[w]), y) - ptseg[w].begin() - 1;
		for (int e = idx + 1; e; e -= e & (-e))
		{
			res += fen[w][e];
		}
		return res;
	}
	int mid = (L + R) >> 1;
	if (a <= mid) res += qry(w << 1, L, mid, a, b, y);
	if (mid < b) res += qry(w << 1 | 1, mid + 1, R, a, b, y);
	return res;
}

void del(int idx, int t, bool flag)
{
	int lt = *prev(lts.UB(idx)), rt = *rts.LB(idx);
	lts.erase(lt); rts.erase(rt);
	if (flag)
	{
		upd(1, 0, N - 1, rt, lt, t - lst[lt]);
	}
	else
	{
		pts[rt].PB(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, bool flag)
{
	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);
		if (flag)
		{
			upd(1, 0, N - 1, idx - 1, lt, t - lst[lt]);
			upd(1, 0, N - 1, rt, idx + 1, t - lst[idx + 1]);
			lst[lt] = t;
		}
		else
		{
			pts[idx - 1].PB(lt);
			pts[rt].PB(idx + 1);
		}
	}
	else if (rts.find(idx - 1) != rts.end())
	{
		int lt = *prev(lts.UB(idx));
		rts.erase(idx - 1);
		rts.insert(idx);
		if (flag)
		{
			upd(1, 0, N - 1, idx - 1, lt, t - lst[lt]);
			lst[lt] = t;
		}
		else
		{
			pts[idx - 1].PB(lt);
		}
	}
	else if (lts.find(idx + 1) != lts.end())
	{
		int rt = *rts.LB(idx);
		lts.erase(idx + 1);
		lts.insert(idx);
		if (flag)
		{
			upd(1, 0, N - 1, rt, idx + 1, t - lst[idx + 1]);
			//update(idx + 1, rt) with t - ls.
			lst[idx] = t;
		}
		else
		{
			pts[rt].PB(idx + 1);
		}
	}
	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};
		}
	}
	FOR(i, 0, Q)
	{
		if (quer[i].fi == -1)
		{
			int idx = quer[i].se;
			if (!state[idx])
			{
				ins(idx, i, 0);
			}
			else
			{
				del(idx, i, 0);
			}
			state[idx] = state[idx] ^ 1;
		}
	}
	FOR(i, 0, Q)
	{
		if (quer[i].fi == -1)
		{
			int idx = quer[i].se;
			state[idx] = state[idx] ^ 1;
		}
	}
	build(1, 0, N - 1);
	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, 1);
			}
			else
			{
				del(idx, i, 1);
			}
			state[idx] = state[idx] ^ 1;
		}
		else
		{
			int lt = quer[i].fi, rt = quer[i].se;
			ans = qry(1, 0, N - 1, rt, N - 1, lt);
			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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 58104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 374 ms 65784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 58232 KB Output is correct
2 Correct 56 ms 58232 KB Output is correct
3 Correct 56 ms 58308 KB Output is correct
4 Correct 54 ms 58240 KB Output is correct
5 Correct 2971 ms 130652 KB Output is correct
6 Correct 2681 ms 128184 KB Output is correct
7 Correct 2048 ms 117640 KB Output is correct
8 Correct 332 ms 87564 KB Output is correct
9 Correct 145 ms 63736 KB Output is correct
10 Correct 155 ms 64248 KB Output is correct
11 Correct 156 ms 64532 KB Output is correct
12 Correct 323 ms 86284 KB Output is correct
13 Correct 338 ms 87604 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 58232 KB Output is correct
2 Incorrect 56 ms 58240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 58104 KB Output isn't correct
2 Halted 0 ms 0 KB -