#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)
~~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |