oj.uz

Submission #276488

# Submission time Handle Problem Language Result Execution time Memory
276488 2020-08-20T13:11:41 Z srvlt Street Lamps (APIO19_street_lamps) C++14
20 / 100
 4851 ms 140136 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 = 300003;
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;
}

// n global/local

struct SegTree {
	int n;
	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 = 1;
		while (n < SZ(xv)) n <<= 1;
		val.resize(n << 1);
	}
	void upd(int x, int y) {
		x = pos(x);
		for (x += n; x > 0; x >>= 1)
			val[x] += y;
	}
	int getsum(int l, int r) {
		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 += val[--r];
			if (l & 1) res += val[l++];
		}		
		return res;
	}
};

struct SegTree2D {
	int n;
	vector <int> xv;
	vector <array <int, 2>> pt;
	vector <SegTree> 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) {
		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(pos(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, int r2) {
		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, r2);
			if (l & 1) res += nd[l++].getsum(l2, r2);
		}
		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 <= n; i++)
		//cerr << get(i) - get(i - 1) << ' ';
	//cerr << '\n';
	//for (int i = 1; i <= n; i++)
		//cerr << lamps.getsum(i, i, 1, n) << ' ';
	//cerr << '\n';
	//exit(0);
	for (int i = 1; i <= q; i++) {
		if (qr[i][0] == 1) {
			int l = qr[i][1], r = qr[i][2] - 1;
			int res = 0;
			if (get(r) - get(l - 1) == r - l + 1)
				res -= (q - i);
			res += lamps.getsum(1, l, r, n);
			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 1536 KB Output is correct
2 Correct 2 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 418 ms 17264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1792 KB Output is correct
2 Correct 5 ms 1792 KB Output is correct
3 Correct 4 ms 1792 KB Output is correct
4 Correct 2 ms 1536 KB Output is correct
5 Correct 4708 ms 126836 KB Output is correct
6 Correct 3881 ms 121680 KB Output is correct
7 Correct 2617 ms 79964 KB Output is correct
8 Correct 153 ms 13528 KB Output is correct
9 Incorrect 100 ms 8056 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1664 KB Output is correct
2 Correct 3 ms 1792 KB Output is correct
3 Correct 5 ms 1792 KB Output is correct
4 Correct 5 ms 1920 KB Output is correct
5 Correct 748 ms 59872 KB Output is correct
6 Correct 1906 ms 75516 KB Output is correct
7 Correct 3240 ms 116984 KB Output is correct
8 Correct 4851 ms 140136 KB Output is correct
9 Correct 606 ms 23896 KB Output is correct
10 Incorrect 521 ms 23752 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 1536 KB Output is correct
2 Correct 2 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 418 ms 17264 KB Output isn't correct
9 Halted 0 ms 0 KB -