oj.uz

Submission #276533

# Submission time Handle Problem Language Result Execution time Memory
276533 2020-08-20T13:32:30 Z srvlt Street Lamps (APIO19_street_lamps) C++14
20 / 100
 4523 ms 108420 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 3e5 + 123;
int N, q, fen[n0];
char s[n0], s0[n0];

void upd(int x, int y) {
	for (; x <= N; x |= (x + 1)) fen[x] += y;
}

int get(int x) {
	int res = 0;
	for (; x >= 0; x = (x & (x + 1)) - 1) res += fen[x];
	return res;
}

int get_left(int x) {
	int l = 0, r = x;
	while (l < r - 1) {
		int mid = l + r >> 1;
		if (get(x) - get(mid - 1) == x - mid + 1) r = mid;
		else l = mid;
	}
	return r;
}

int get_right(int x) {
	int l = x, r = N + 1;
	while (l < r - 1) {
		int mid = l + r >> 1;
		if (get(mid) - get(x - 1) == mid - x + 1) l = mid;
		else r = mid;
	}
	return l;
}

struct Fen {
	int n, s = 0;
	vector <int> xv, val;
	int pos(int x) {
		return (int)(lower_bound(all(xv), x) - begin(xv));
	}
	void add(int x) {
		xv.pb(x);
	}
	void init() {
		cps(xv);
		n = SZ(xv);
		val.resize(n);
	}
	void upd(int x, int y) {
		x = pos(x);
		s += y;
		for (; x < n; x |= (x + 1)) val[x] += y;
	}
	int getsum(int x) {
		x = pos(x) - 1;
		int res = 0;
		for (; x >= 0; x = (x & (x + 1)) - 1) res += val[x];
		return s - res;
	}
};

struct SegTree2D {
	int n;
	vector <int> xv;
	vector <array <int, 2>> pt;
	vector <Fen> nd;
	int pos(int x) {
		return (int)(lower_bound(all(xv), x) - begin(xv));
	}
	void add(int x, int y) {
		xv.pb(x);
		pt.pb({x, y});
	}
	void reserve(int x, int y) {
		x = pos(x);
		for (x += n; x > 0; x >>= 1)
			nd[x].add(y);
	}
	void init() {
		cps(xv);
		n = 1;
		while (n < SZ(xv)) n <<= 1;
		nd.resize(n << 1);
		for (auto & i : pt)
			reserve(i[0], i[1]);
		for (int i = 1; i < (n << 1); i++)
			nd[i].init();
	}
	void upd(int x, int y, int val) {
		x = pos(x);
		for (x += n; x > 0; x >>= 1)
			nd[x].upd(y, val);
	}
	int getsum(int l, int r, int l2) {
		l = pos(l), r = pos(r + 1);
		int res = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (r & 1) res += nd[--r].getsum(l2);
			if (l & 1) res += nd[l++].getsum(l2);
		}
		return res;
	}
};
SegTree2D lamps;
int qr[n0][3];

void toggle(int x) {
	if (s[x] == '1') {
		s[x] = '0';
		upd(x, -1);
	}	else {
		s[x] = '1';
		upd(x, 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> q;
	for (int i = 1; i <= N; i++) {
		cin >> s[i];
		s0[i] = s[i];
		if (s[i] == '1') {
			upd(i, 1);
		}	else if (s[i - 1] == '1') {
			int l = get_left(i - 1);
			lamps.add(l, i - 1);
		}
	}
	lamps.add(get_left(N), N);
	string tp;
	for (int i = 1; i <= q; i++) {
		cin >> tp;
		if (tp == "query") {
			qr[i][0] = 1;
			cin >> qr[i][1] >> qr[i][2];
		}	else {
			qr[i][0] = 2;
			cin >> qr[i][1];
			int x = qr[i][1];
			if (s[x] == '1') {
				toggle(x);
				if (s[x - 1] == '1') {
					int l = get_left(x - 1);
					lamps.add(l, x - 1);
				}
				if (s[x + 1] == '1') {
					int r = get_right(x + 1);
					lamps.add(x + 1, r);
				}
			}	else {
				toggle(x);
				int l = get_left(x);
				int r = get_right(x);
				lamps.add(l, r);
			}
		}
	}
	lamps.init();
	memset(& fen, 0, sizeof(fen));
	for (int i = 1; i <= N; i++) {
		s[i] = s0[i];
		if (s[i] == '1') {
			upd(i, 1);
		}	else if (s[i - 1] == '1') {
			int l = get_left(i - 1);
			lamps.upd(l, i - 1, q);
		}
	}
	lamps.upd(get_left(N), N, q);
	for (int i = 1; i <= q; i++) {
		if (qr[i][0] == 1) {
			int l = qr[i][1], r = qr[i][2];
			r--;
			int res = 0;
			if (get(r) - get(l - 1) == r - l + 1)
				res -= (q - i);
			res += lamps.getsum(1, l, r);
			cout << res << '\n';
		}	else {
			int x = qr[i][1];
			if (s[x] == '1') {
				int l = get_left(x), r = get_right(x);
				lamps.upd(l, r, -(q - i));
				toggle(x);
				if (s[x - 1] == '1')
					lamps.upd(l, x - 1, q - i);
				if (s[x + 1] == '1')
					lamps.upd(x + 1, r, q - i);
			}	else {
				int l = x, r = x;
				if (s[x - 1] == '1') {
					l = get_left(x - 1);
					lamps.upd(l, x - 1, -(q - i));
				}
				if (s[x + 1] == '1') {
					r = get_right(x + 1);
					lamps.upd(x + 1, r, -(q - i));
				}
				toggle(x);
				lamps.upd(l, r, q - i);
			}
		}
	}
}

Compilation message

street_lamps.cpp: In function 'int get_left(int)':
street_lamps.cpp:28:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In function 'int get_right(int)':
street_lamps.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 331 ms 15304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1732 KB Output is correct
2 Correct 4 ms 1792 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 1 ms 1536 KB Output is correct
5 Correct 4217 ms 92880 KB Output is correct
6 Correct 3585 ms 88284 KB Output is correct
7 Correct 2353 ms 57572 KB Output is correct
8 Correct 148 ms 8952 KB Output is correct
9 Incorrect 99 ms 6564 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1664 KB Output is correct
2 Correct 3 ms 1704 KB Output is correct
3 Correct 5 ms 1664 KB Output is correct
4 Correct 5 ms 1792 KB Output is correct
5 Correct 791 ms 43332 KB Output is correct
6 Correct 1772 ms 56924 KB Output is correct
7 Correct 3126 ms 84336 KB Output is correct
8 Correct 4523 ms 108420 KB Output is correct
9 Correct 584 ms 22036 KB Output is correct
10 Incorrect 486 ms 22064 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1528 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 1 ms 1536 KB Output is correct
5 Correct 2 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 1 ms 1536 KB Output is correct
8 Incorrect 331 ms 15304 KB Output isn't correct
9 Halted 0 ms 0 KB -