oj.uz

Submission #187132

# Submission time Handle Problem Language Result Execution time Memory
187132 2020-01-12T13:02:28 Z KCSC Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2092 ms 56516 KB 
#include <bits/stdc++.h>
using namespace std;

const int DIM = 300005;

char ini[DIM];
int bit[DIM], ans[DIM];

struct Segment {
	int st, en, vl;

	bool operator <(const Segment &other) const {
		return st < other.st;
	}
}; set<Segment> mst;

struct Event {
	int st, en, tm, tp;

	bool operator <(const Event &other) const {
		return make_pair(st, en) < make_pair(other.st, other.en);
	}
}; vector<Event> evn;

void update(int ps, int vl) {
	for (; ps < DIM; ps += (ps & -ps))
		bit[ps] += vl;
}

int query(int ps, int vl = 0) {
	for (; ps > 0; ps -= (ps & -ps))
		vl += bit[ps];
	return vl;
}

void newRectangle(int st, int en, int vl) {
	evn.push_back({st, st, vl, 1});
	evn.push_back({st, en + 1, -vl, 1});
	evn.push_back({en + 1, st, -vl, 1});
	evn.push_back({en + 1, en + 1, vl, 1});
} 

void divide(int le, int ri) {
	if (le == ri)
		return;
	int md = (le + ri) >> 1;
	divide(le, md); divide(md + 1, ri);
	// now solve subtask 4 considering only toggles from {le, md} and queries from {md + 1, ri}
	vector<Event> upd, qry;
	for (int i = le; i <= md; ++i) 
		if (evn[i].tp == 1)
			upd.push_back(evn[i]);
	sort(upd.begin(), upd.end());
	for (int i = md + 1; i <= ri; ++i)
		if (evn[i].tp == 2)
			qry.push_back(evn[i]);
	sort(qry.begin(), qry.end());
	int pt = 0;
	for (Event qr : qry) {
		for (; pt < upd.size() and upd[pt].st <= qr.st; ++pt)
			update(upd[pt].en, upd[pt].tm);
		ans[qr.tm] += query(qr.en);
	}
	for (--pt; pt >= 0; --pt)
		update(upd[pt].en, -upd[pt].tm);
}

int main(void) {
#ifdef HOME
	freopen("street.in", "r", stdin);
	freopen("street.out", "w", stdout);
#endif
	int n, q; cin >> n >> q;
	cin >> (ini + 1);
	for (int i = 1; i <= n; ++i) {
		if (ini[i] == '0')
			continue;
		int st = i, en = i;
		while (ini[en + 1] == '1')
			++en;
		mst.insert({st, en, 1});	
		i = en;
	}
	for (int i = 1; i <= q; ++i) {
		string aux; cin >> aux;
		if (aux == "toggle") {
			int p; cin >> p;
			if (ini[p] == '0') {
				int st = p, en = p;
				auto it = mst.lower_bound({p + 1, -1, -1});
				if (it != mst.end() and it -> st == p + 1) {
					newRectangle(it -> st, it -> en, i + 1 - it -> vl);
					en = it -> en; it = mst.erase(it);
				}
				if (it != mst.begin() and prev(it) -> en == p - 1) {
					--it;
					newRectangle(it -> st, it -> en, i + 1 - it -> vl);
					st = it -> st; it = mst.erase(it);
				}
				mst.insert({st, en, i + 1});
				ini[p] = '1';
			} else {
				auto it = --mst.lower_bound({p + 1, -1, -1});
				newRectangle(it -> st, it -> en, i + 1 - it -> vl);
				vector<Segment> auxSeg;
				if (it -> st < p)
					auxSeg.push_back({it -> st, p - 1, i + 1});
				if (p < it -> en) 
					auxSeg.push_back({p + 1, it -> en, i + 1});
				mst.erase(it);
				for (Segment sg : auxSeg)
					mst.insert(sg);
				ini[p] = '0';
			}
			ans[i] = -1;
		} else {
			int st, en; cin >> st >> en; --en;
			evn.push_back({st, en, i, 2});
			auto it = mst.lower_bound({st + 1, -1, -1});
			if (it != mst.begin()) {
				--it;
				if (it -> st <= st and en <= it -> en)
					ans[i] += i + 1 - it -> vl;
			}
		}
	}
	divide(0, evn.size() - 1);
	for (int i = 1; i <= q; ++i)
		if (ans[i] >= 0)
			cout << ans[i] << "\n";
	return 0;
}

Compilation message

street_lamps.cpp: In function 'void divide(int, int)':
street_lamps.cpp:60:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; pt < upd.size() and upd[pt].st <= qr.st; ++pt)
          ~~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1429 ms 29400 KB Output is correct
2 Correct 1415 ms 29868 KB Output is correct
3 Correct 1406 ms 30436 KB Output is correct
4 Correct 1664 ms 37528 KB Output is correct
5 Correct 1822 ms 40300 KB Output is correct
6 Correct 1457 ms 40804 KB Output is correct
7 Correct 785 ms 19028 KB Output is correct
8 Correct 787 ms 19024 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 1912 ms 52148 KB Output is correct
6 Correct 2092 ms 52144 KB Output is correct
7 Correct 1842 ms 37324 KB Output is correct
8 Correct 819 ms 19240 KB Output is correct
9 Correct 426 ms 11936 KB Output is correct
10 Correct 466 ms 14800 KB Output is correct
11 Correct 472 ms 15108 KB Output is correct
12 Correct 811 ms 19184 KB Output is correct
13 Correct 822 ms 19096 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 500 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 10 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 1095 ms 25356 KB Output is correct
6 Correct 1297 ms 34760 KB Output is correct
7 Correct 1477 ms 40668 KB Output is correct
8 Correct 1732 ms 56516 KB Output is correct
9 Correct 1198 ms 35764 KB Output is correct
10 Correct 1386 ms 48852 KB Output is correct
11 Correct 1233 ms 35824 KB Output is correct
12 Correct 1404 ms 48784 KB Output is correct
13 Correct 1225 ms 35692 KB Output is correct
14 Correct 1420 ms 48652 KB Output is correct
15 Correct 830 ms 19048 KB Output is correct
16 Correct 826 ms 19148 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 1429 ms 29400 KB Output is correct
9 Correct 1415 ms 29868 KB Output is correct
10 Correct 1406 ms 30436 KB Output is correct
11 Correct 1664 ms 37528 KB Output is correct
12 Correct 1822 ms 40300 KB Output is correct
13 Correct 1457 ms 40804 KB Output is correct
14 Correct 785 ms 19028 KB Output is correct
15 Correct 787 ms 19024 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 6 ms 504 KB Output is correct
18 Correct 4 ms 504 KB Output is correct
19 Correct 4 ms 376 KB Output is correct
20 Correct 1912 ms 52148 KB Output is correct
21 Correct 2092 ms 52144 KB Output is correct
22 Correct 1842 ms 37324 KB Output is correct
23 Correct 819 ms 19240 KB Output is correct
24 Correct 426 ms 11936 KB Output is correct
25 Correct 466 ms 14800 KB Output is correct
26 Correct 472 ms 15108 KB Output is correct
27 Correct 811 ms 19184 KB Output is correct
28 Correct 822 ms 19096 KB Output is correct
29 Correct 4 ms 500 KB Output is correct
30 Correct 5 ms 504 KB Output is correct
31 Correct 10 ms 504 KB Output is correct
32 Correct 5 ms 504 KB Output is correct
33 Correct 1095 ms 25356 KB Output is correct
34 Correct 1297 ms 34760 KB Output is correct
35 Correct 1477 ms 40668 KB Output is correct
36 Correct 1732 ms 56516 KB Output is correct
37 Correct 1198 ms 35764 KB Output is correct
38 Correct 1386 ms 48852 KB Output is correct
39 Correct 1233 ms 35824 KB Output is correct
40 Correct 1404 ms 48784 KB Output is correct
41 Correct 1225 ms 35692 KB Output is correct
42 Correct 1420 ms 48652 KB Output is correct
43 Correct 830 ms 19048 KB Output is correct
44 Correct 826 ms 19148 KB Output is correct
45 Correct 870 ms 17796 KB Output is correct
46 Correct 923 ms 18400 KB Output is correct
47 Correct 1029 ms 21608 KB Output is correct
48 Correct 1845 ms 37588 KB Output is correct
49 Correct 532 ms 16376 KB Output is correct
50 Correct 532 ms 16344 KB Output is correct
51 Correct 540 ms 16408 KB Output is correct
52 Correct 572 ms 17112 KB Output is correct
53 Correct 550 ms 16788 KB Output is correct
54 Correct 546 ms 16836 KB Output is correct