oj.uz

답안 #167611

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167611 2019-12-09T05:58:55 Z qkxwsm 가로등 (APIO19_street_lamps) C++14
20 / 100
 3335 ms 163260 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

#define int long long

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 56 ms 58104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 58360 KB Output is correct
2 Correct 58 ms 58488 KB Output is correct
3 Correct 58 ms 58360 KB Output is correct
4 Correct 56 ms 58220 KB Output is correct
5 Correct 3335 ms 163260 KB Output is correct
6 Correct 3004 ms 156208 KB Output is correct
7 Correct 2393 ms 136184 KB Output is correct
8 Correct 342 ms 84492 KB Output is correct
9 Correct 148 ms 65404 KB Output is correct
10 Correct 156 ms 66008 KB Output is correct
11 Correct 158 ms 66000 KB Output is correct
12 Correct 325 ms 83184 KB Output is correct
13 Correct 333 ms 84616 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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