oj.uz

Submission #564191

# Submission time Handle Problem Language Result Execution time Memory
564191 2022-05-18T17:22:59 Z ngpin04 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 3282 ms 128656 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 3e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> posy[N];
vector <int> bit[N];

int op[N];
int l[N];
int r[N];
int a[N];
int n,q;

void fakeupdate(int x, int y) {
	for (; x <= n; x += x & -x) 
		posy[x].push_back(y);
}

void fakeget(int x, int y) {
	for (; x; x -= x & -x)
		posy[x].push_back(y);
}

void fakeupdate(int x, int u, int y, int v) {
	if (x > u || y > v)
		return;
	fakeupdate(x, y), fakeupdate(u + 1, v + 1);
	fakeupdate(x, v + 1), fakeupdate(u + 1, y);
}

void update(int x, int y, int val) {
	// cerr << x << " " << y << " " << val << "\n";
	for (; x <= n; x += x & -x) {
		int s = lower_bound(ALL(posy[x]), y) - posy[x].begin() + 1;
		for (int i = s; i < (int) bit[x].size(); i += i & -i)
			bit[x][i] += val;
	}
}

int get(int x, int y) {
	int res = 0;
	for (; x > 0; x -= x & -x) {
		int s = lower_bound(ALL(posy[x]), y) - posy[x].begin() + 1;
		for (int i = s; i > 0; i -= i & -i)
			res += bit[x][i];
	}
	return res;
}

void update(int x, int u, int y, int v, int val) {
	if (x > u || y > v)
		return;
	// cerr << x << " " << y << " " << u << " " << v << " " << val << "\n";
	update(x, y, val), update(u + 1, v + 1, val);
	update(x, v + 1, -val), update(u + 1, y, -val);
}

void build() {
	set <pair <int, int>> seg;
	for (int i = 1; i <= n; i++) if (a[i]) {
		int j = i;
		while (a[j])
			j++;

		seg.insert(mp(i, j - 1));
		i = j;
	}

	for (pair <int, int> s : seg)
		fakeupdate(s.fi, s.se, s.fi, s.se);

	for (int i = 1; i <= q; i++) {
		if (op[i] == 0) {
			int pos = l[i];
			if (a[pos]) {
				auto cur = *prev(seg.upper_bound(mp(pos, oo)));
				fakeupdate(cur.fi, pos, pos, cur.se);
				seg.erase(cur);
				if (cur.fi < pos)
					seg.insert(mp(cur.fi, pos - 1));
				if (pos < cur.se)
					seg.insert(mp(pos + 1, cur.se));
			} else {	
				auto it = seg.upper_bound(mp(pos, oo));
				auto f = (it == seg.begin()) ? mp(-1, -1) : *(--(it));
				auto g = (it == seg.end()) ? mp(oo, oo) : *it;
				int l = pos, r = pos;
				if (f.se == l - 1)
					l = f.fi;
				if (g.fi == r + 1)
					r = g.se;

				fakeupdate(l, pos, pos, r);
				seg.insert(mp(l, r));
			}

			a[pos] ^= 1;
		} else {
			fakeget(l[i], r[i]);
		}
	}

	for (int i = 1; i <= n; i++) {
		sort(ALL(posy[i]));
		posy[i].resize(unique(ALL(posy[i])) - posy[i].begin());
		bit[i].assign(posy[i].size() + 1, 0);
	}

	for (int i = 1; i <= q; i++) 
		if (op[i] == 0)
			a[l[i]] ^= 1;
}

void solve() {
	set <pair <int, int>> seg;
	for (int i = 1; i <= n; i++) if (a[i]) {
		int j = i;
		while (a[j])
			j++;

		seg.insert(mp(i, j - 1));
		i = j;
	}

	for (pair <int, int> s : seg) 
		update(s.fi, s.se, s.fi, s.se, q);

	for (int i = 1; i <= q; i++) {

		if (op[i] == 0) {
			int pos = l[i];
			if (a[pos]) {
				auto cur = *prev(seg.upper_bound(mp(pos, oo)));

				update(cur.fi, pos, pos, cur.se, -(q - i));
				seg.erase(cur);
				if (cur.fi < pos)
					seg.insert(mp(cur.fi, pos - 1));
				if (pos < cur.se)
					seg.insert(mp(pos + 1, cur.se));
			} else {	
				auto it = seg.upper_bound(mp(pos, oo));
				auto f = (it == seg.begin()) ? mp(-1, -1) : *prev(it);
				auto g = (it == seg.end()) ? mp(oo, oo) : *it;
				int l = pos, r = pos;
				if (f.se == l - 1) {
					seg.erase(f);
					l = f.fi;
				}
				if (g.fi == r + 1) {
					seg.erase(g);
					r = g.se;
				}
				update(l, pos, pos, r, q - i);
				seg.insert(mp(l, r));
			}

			a[pos] ^= 1;
		} else {
			auto it = seg.upper_bound(mp(l[i], oo));
			int ans = get(l[i], r[i]);
			if (it != seg.begin() && (--it)->se >= r[i]) 
				ans -= q - i;

			cout << ans << "\n";
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> q;
	{
		string str; cin >> str;
		for (int i = 1; i <= n; i++)
			a[i] = str[i - 1] - '0';
	}


	for (int i = 1; i <= q; i++) {
		string qr; cin >> qr;
		if (qr == "query") {
			op[i] = 1;
			cin >> l[i] >> r[i];
		} else
			cin >> l[i];
		r[i]--;
	}

	build();
	solve();
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 34392 KB Output is correct
2 Correct 414 ms 41020 KB Output is correct
3 Correct 697 ms 50400 KB Output is correct
4 Correct 2382 ms 103012 KB Output is correct
5 Correct 2150 ms 102376 KB Output is correct
6 Correct 2469 ms 106728 KB Output is correct
7 Correct 773 ms 58760 KB Output is correct
8 Correct 771 ms 60136 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14676 KB Output is correct
2 Correct 10 ms 14688 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 2874 ms 124896 KB Output is correct
6 Correct 2670 ms 119960 KB Output is correct
7 Correct 2148 ms 102924 KB Output is correct
8 Correct 800 ms 61284 KB Output is correct
9 Correct 127 ms 24504 KB Output is correct
10 Correct 128 ms 25204 KB Output is correct
11 Correct 139 ms 25656 KB Output is correct
12 Correct 752 ms 59924 KB Output is correct
13 Correct 784 ms 61412 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14608 KB Output is correct
2 Correct 9 ms 14596 KB Output is correct
3 Correct 10 ms 14548 KB Output is correct
4 Correct 11 ms 14676 KB Output is correct
5 Correct 1333 ms 84992 KB Output is correct
6 Correct 1869 ms 97680 KB Output is correct
7 Correct 2482 ms 108320 KB Output is correct
8 Correct 3282 ms 128656 KB Output is correct
9 Correct 527 ms 45024 KB Output is correct
10 Correct 443 ms 40844 KB Output is correct
11 Correct 522 ms 44904 KB Output is correct
12 Correct 440 ms 40604 KB Output is correct
13 Correct 526 ms 44988 KB Output is correct
14 Correct 459 ms 41020 KB Output is correct
15 Correct 775 ms 59988 KB Output is correct
16 Correct 804 ms 61292 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 309 ms 34392 KB Output is correct
9 Correct 414 ms 41020 KB Output is correct
10 Correct 697 ms 50400 KB Output is correct
11 Correct 2382 ms 103012 KB Output is correct
12 Correct 2150 ms 102376 KB Output is correct
13 Correct 2469 ms 106728 KB Output is correct
14 Correct 773 ms 58760 KB Output is correct
15 Correct 771 ms 60136 KB Output is correct
16 Correct 9 ms 14676 KB Output is correct
17 Correct 10 ms 14688 KB Output is correct
18 Correct 9 ms 14548 KB Output is correct
19 Correct 8 ms 14548 KB Output is correct
20 Correct 2874 ms 124896 KB Output is correct
21 Correct 2670 ms 119960 KB Output is correct
22 Correct 2148 ms 102924 KB Output is correct
23 Correct 800 ms 61284 KB Output is correct
24 Correct 127 ms 24504 KB Output is correct
25 Correct 128 ms 25204 KB Output is correct
26 Correct 139 ms 25656 KB Output is correct
27 Correct 752 ms 59924 KB Output is correct
28 Correct 784 ms 61412 KB Output is correct
29 Correct 9 ms 14608 KB Output is correct
30 Correct 9 ms 14596 KB Output is correct
31 Correct 10 ms 14548 KB Output is correct
32 Correct 11 ms 14676 KB Output is correct
33 Correct 1333 ms 84992 KB Output is correct
34 Correct 1869 ms 97680 KB Output is correct
35 Correct 2482 ms 108320 KB Output is correct
36 Correct 3282 ms 128656 KB Output is correct
37 Correct 527 ms 45024 KB Output is correct
38 Correct 443 ms 40844 KB Output is correct
39 Correct 522 ms 44904 KB Output is correct
40 Correct 440 ms 40604 KB Output is correct
41 Correct 526 ms 44988 KB Output is correct
42 Correct 459 ms 41020 KB Output is correct
43 Correct 775 ms 59988 KB Output is correct
44 Correct 804 ms 61292 KB Output is correct
45 Correct 128 ms 24032 KB Output is correct
46 Correct 225 ms 28776 KB Output is correct
47 Correct 1138 ms 58208 KB Output is correct
48 Correct 2337 ms 104132 KB Output is correct
49 Correct 145 ms 26436 KB Output is correct
50 Correct 149 ms 26168 KB Output is correct
51 Correct 154 ms 26712 KB Output is correct
52 Correct 183 ms 28684 KB Output is correct
53 Correct 189 ms 28664 KB Output is correct
54 Correct 189 ms 28504 KB Output is correct