oj.uz

답안 #167608

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167608 2019-12-09T05:34:59 Z qkxwsm 가로등 (APIO19_street_lamps) C++14
20 / 100
 2918 ms 130528 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 y1, int y2)
{
	// if (w == 1)
	// {
	// 	cerr << "QUERY " << a << ' ' << b << ' ' << y1 << ' ' << y2 << endl;
	// }
	if (a <= L && R <= b)
	{
		int res = 0;
		int idx = UB(ALL(ptseg[w]), y2) - ptseg[w].begin() - 1;
		for (int e = idx + 1; e; e -= e & (-e))
		{
			res += fen[w][e];
		}
		idx = UB(ALL(ptseg[w]), y1 - 1) - ptseg[w].begin() - 1;
		for (int e = idx + 1; e; e -= e & (-e))
		{
			res -= fen[w][e];
		}
		return res;
	}
	int mid = (L + R) >> 1, res = 0;
	if (a <= mid) res += qry(w << 1, L, mid, a, b, y1, y2);
	if (mid < b) res += qry(w << 1 | 1, mid + 1, R, a, b, y1, y2);
	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, lt, rt, t - lst[lt]);
	}
	else
	{
		pts[lt].PB(rt);
	}
	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, lt, idx - 1, t - lst[lt]);
			upd(1, 0, N - 1, idx + 1, rt, t - lst[idx + 1]);
			lst[lt] = t;
		}
		else
		{
			pts[lt].PB(idx - 1);
			pts[idx + 1].PB(rt);
		}
	}
	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, lt, idx - 1, t - lst[lt]);
			lst[lt] = t;
		}
		else
		{
			pts[lt].PB(idx - 1);
		}
	}
	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, idx + 1, rt, t - lst[idx + 1]);
			//update(idx + 1, rt) with t - ls.
			lst[idx] = t;
		}
		else
		{
			pts[idx + 1].PB(rt);
		}
	}
	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, 0, lt, rt, N - 1);
			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 54 ms 58108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 58236 KB Output is correct
2 Correct 56 ms 58240 KB Output is correct
3 Correct 56 ms 58360 KB Output is correct
4 Correct 55 ms 58360 KB Output is correct
5 Correct 2918 ms 130528 KB Output is correct
6 Correct 2796 ms 128588 KB Output is correct
7 Correct 2278 ms 117780 KB Output is correct
8 Correct 360 ms 87584 KB Output is correct
9 Correct 159 ms 63832 KB Output is correct
10 Correct 170 ms 64212 KB Output is correct
11 Correct 168 ms 64348 KB Output is correct
12 Correct 345 ms 86272 KB Output is correct
13 Correct 362 ms 87656 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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