oj.uz

Submission #444902

# Submission time Handle Problem Language Result Execution time Memory
444902 2021-07-15T20:01:27 Z sinamhdv Street Lamps (APIO19_street_lamps) C++11
100 / 100
 2116 ms 78812 KB 
// 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1144 ms 45016 KB Output is correct
2 Correct 1367 ms 47988 KB Output is correct
3 Correct 1331 ms 44908 KB Output is correct
4 Correct 1290 ms 49236 KB Output is correct
5 Correct 1480 ms 64180 KB Output is correct
6 Correct 966 ms 39708 KB Output is correct
7 Correct 1971 ms 75812 KB Output is correct
8 Correct 1952 ms 70108 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 572 ms 26292 KB Output is correct
6 Correct 994 ms 43856 KB Output is correct
7 Correct 1516 ms 63888 KB Output is correct
8 Correct 2116 ms 70128 KB Output is correct
9 Correct 993 ms 52748 KB Output is correct
10 Correct 1124 ms 60528 KB Output is correct
11 Correct 988 ms 58532 KB Output is correct
12 Correct 2055 ms 75748 KB Output is correct
13 Correct 2072 ms 70132 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 2092 ms 78812 KB Output is correct
6 Correct 1541 ms 59536 KB Output is correct
7 Correct 1012 ms 39712 KB Output is correct
8 Correct 477 ms 16424 KB Output is correct
9 Correct 823 ms 26424 KB Output is correct
10 Correct 429 ms 6452 KB Output is correct
11 Correct 835 ms 26404 KB Output is correct
12 Correct 422 ms 6588 KB Output is correct
13 Correct 829 ms 26384 KB Output is correct
14 Correct 425 ms 6468 KB Output is correct
15 Correct 2047 ms 76088 KB Output is correct
16 Correct 2106 ms 70052 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1144 ms 45016 KB Output is correct
9 Correct 1367 ms 47988 KB Output is correct
10 Correct 1331 ms 44908 KB Output is correct
11 Correct 1290 ms 49236 KB Output is correct
12 Correct 1480 ms 64180 KB Output is correct
13 Correct 966 ms 39708 KB Output is correct
14 Correct 1971 ms 75812 KB Output is correct
15 Correct 1952 ms 70108 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 2 ms 972 KB Output is correct
18 Correct 2 ms 972 KB Output is correct
19 Correct 2 ms 716 KB Output is correct
20 Correct 572 ms 26292 KB Output is correct
21 Correct 994 ms 43856 KB Output is correct
22 Correct 1516 ms 63888 KB Output is correct
23 Correct 2116 ms 70128 KB Output is correct
24 Correct 993 ms 52748 KB Output is correct
25 Correct 1124 ms 60528 KB Output is correct
26 Correct 988 ms 58532 KB Output is correct
27 Correct 2055 ms 75748 KB Output is correct
28 Correct 2072 ms 70132 KB Output is correct
29 Correct 2 ms 716 KB Output is correct
30 Correct 2 ms 844 KB Output is correct
31 Correct 2 ms 716 KB Output is correct
32 Correct 1 ms 716 KB Output is correct
33 Correct 2092 ms 78812 KB Output is correct
34 Correct 1541 ms 59536 KB Output is correct
35 Correct 1012 ms 39712 KB Output is correct
36 Correct 477 ms 16424 KB Output is correct
37 Correct 823 ms 26424 KB Output is correct
38 Correct 429 ms 6452 KB Output is correct
39 Correct 835 ms 26404 KB Output is correct
40 Correct 422 ms 6588 KB Output is correct
41 Correct 829 ms 26384 KB Output is correct
42 Correct 425 ms 6468 KB Output is correct
43 Correct 2047 ms 76088 KB Output is correct
44 Correct 2106 ms 70052 KB Output is correct
45 Correct 562 ms 24492 KB Output is correct
46 Correct 835 ms 28984 KB Output is correct
47 Correct 771 ms 28876 KB Output is correct
48 Correct 1330 ms 48912 KB Output is correct
49 Correct 1315 ms 65328 KB Output is correct
50 Correct 1366 ms 65444 KB Output is correct
51 Correct 1159 ms 65188 KB Output is correct
52 Correct 835 ms 62892 KB Output is correct
53 Correct 836 ms 61604 KB Output is correct
54 Correct 846 ms 63288 KB Output is correct