Submission #444902

#	Time	Username	Problem	Language	Result	Execution time	Memory
444902		sinamhdv	Street Lamps (APIO19_street_lamps)	C++11	100 / 100	2116 ms	78812 KiB

street_lamps

// APIO19_street_lamps
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 300100;
const int LOGN = 25;

int n, q;
bool a[MAXN];
ll afen[MAXN];
set<int> zer;
vector<pair<pii, int>> qvec;
char op[MAXN];
int ql[MAXN], qr[MAXN];
int ind[MAXN];
int qv;

ll fen[LOGN][MAXN];
pii seg[LOGN][MAXN];

inline void fenadd(ll *fen, int i, int x)
{
	for (i++; i < MAXN; i += i & -i) fen[i] += x;
}

inline ll fenpget(ll *fen, int i)
{
	ll res = 0;
	for (i++; i > 0; i -= i & -i) res += fen[i];
	return res;
}

inline ll fenget(ll *fen, int l, int r)
{
	return fenpget(fen, r) - fenpget(fen, l - 1);
}

inline void fenaddlr(ll *fen, int l, int r, int x)
{
	fenadd(fen, l, x);
	fenadd(fen, r + 1, -x);
}

void build(int h = 1, int l = 0, int r = qv - 1)
{
	if (l == r)
	{
		seg[h][l] = {qvec[l].fr.sc, l};
		int ql = qvec[l].fr.fr, qr = qvec[l].fr.sc;
		if (fenget(afen, ql, qr) == qr - ql + 1) fenaddlr(fen[h], l, l, q);
		return;
	}
	int mid = (r + l) / 2;
	build(h + 1, l, mid);
	build(h + 1, mid + 1, r);
	merge(seg[h + 1] + l, seg[h + 1] + mid + 1, seg[h + 1] + mid + 1, seg[h + 1] + r + 1, seg[h] + l);
}

void add(int L, int R, int bl, int br, int x, int h = 1, int l = 0, int r = qv - 1)
{
	if (l > R || r < L) return;
	if (l >= L && r <= R)
	{
		bl = lower_bound(seg[h] + l, seg[h] + r + 1, mp(bl, -INF)) - seg[h];
		br = lower_bound(seg[h] + l, seg[h] + r + 1, mp(br + 1, -INF)) - seg[h] - 1;
		fenaddlr(fen[h], bl, br, x);
		return;
	}
	int mid = (r + l) / 2;
	add(L, R, bl, br, x, h + 1, l, mid);
	add(L, R, bl, br, x, h + 1, mid + 1, r);
}

int get(int i, int h = 1, int l = 0, int r = qv - 1)
{
	int pos = lower_bound(seg[h] + l, seg[h] + r + 1, mp(qvec[i].fr.sc, i)) - seg[h];
	if (l == r) return fenpget(fen[h], pos);
	int mid = (r + l) / 2;
	if (i <= mid) return get(i, h + 1, l, mid) + fenpget(fen[h], pos);
	else return get(i, h + 1, mid + 1, r) + fenpget(fen[h], pos);
}

void toggle(int t, int tm)
{
	if (!a[t]) zer.erase(t);

	auto itr = zer.lower_bound(t);
	auto itl = itr;
	int l, r;
	if (itl == zer.begin()) l = 0;
	else l = *(--itl) + 1;
	if (itr == zer.end()) r = n - 1;
	else r = *(itr) - 1;

	int lpos = lower_bound(all(qvec), mp(mp(l, -INF), -INF)) - qvec.begin();
	int rpos = lower_bound(all(qvec), mp(mp(t + 1, -INF), -INF)) - qvec.begin() - 1;

	add(lpos, rpos, t, r, (q - tm - 1) * (a[t] == 0 ? 1 : -1));

	if (a[t]) zer.insert(t);
	a[t] = !a[t];
	fenadd(afen, t, (a[t] == 0 ? -1 : 1));
}

int32_t main(void)
{
	fast_io;
	cin >> n >> q;
	FOR(i, 0, n)
	{
		char c;
		cin >> c;
		a[i] = c - '0';
		if (!a[i]) zer.insert(i);
		else fenadd(afen, i, 1);
	}
	
	FOR(i, 0, q)
	{
		string s;
		cin >> s;
		op[i] = s[0];
		if (op[i] == 't') cin >> ql[i], ql[i]--;
		else
		{
			cin >> ql[i] >> qr[i], ql[i]--, qr[i] -= 2;
			qvec.pb({{ql[i], qr[i]}, i});
		}
	}

	sort(all(qvec));
	FOR(i, 0, (int)qvec.size()) ind[qvec[i].sc] = i;
	qv = qvec.size();

	build();

	FOR(i, 0, q)
	{
		if (op[i] == 't')
			toggle(ql[i], i);
		else
		{
			int ans = get(ind[i]);
			if (fenget(afen, ql[i], qr[i]) == qr[i] - ql[i] + 1) ans -= q - i - 1;
			cout << ans << endl;
		}
	}

	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20