#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
const int inf = 1e9;
#define X first
#define Y second
vector<ii> P;
int n, q;
char s[300007];
vector<ii> Q;
bool compy(ii a, ii b) {
return (ii){a.Y, a.X} < (ii){b.Y, b.X};
}
struct SegmentTree1D {
vector<ii> P;
vector<int> d;
int lv;
SegmentTree1D(int L, int R) {
lv = R - L + 1;
d.resize(2 * lv + 3);
P.resize(lv);
for(int i = 0 ; i < lv ; i++)
P[i] = ::P[L + i];
sort(P.begin(), P.end(), compy);
}
void insert(int w, int l, int r, int miny, int v) {
if(P[r].Y < miny)
return ;
if(P[l].Y >= miny) {
//~ cout << "ins1d on " << l << " " << r << endl;
d[w] += v;
return ;
}
insert(2 * w, l, (l + r) / 2, miny, v);
insert(2 * w + 1, (l + r) / 2 + 1, r, miny, v);
}
int query(int w, int l, int r, ii p) {
if(w >= 2 * lv)
return 0;
if(P[l].Y > p.Y || (P[l].Y == p.Y && P[l].X > p.X))
return 0;
if(p.Y > P[r].Y || (p.Y == P[r].Y && p.X > P[r].X))
return 0;
int res = d[w];
res += query(2 * w, l, (l + r) / 2, p);
res += query(2 * w + 1, (l + r) / 2 + 1, r, p);
return res;
}
void insert(int miny, int v) {
insert(1, 0, lv - 1, miny, v);
}
int query(ii p) {
return query(1, 0, lv - 1, p);
}
};
struct SegmentTree2D {
int lv;
vector<SegmentTree1D*> d;
void build(int w, int l, int r) {
if(w >= 2 * lv)
return ;
d[w] = new SegmentTree1D(l, r);
build(2 * w, l, (l + r) / 2);
build(2 * w + 1, (l + r) / 2 + 1, r);
}
SegmentTree2D() {
lv = 2;
while(lv < P.size())
lv *= 2;
while(P.size() < lv)
P.push_back({inf, inf});
sort(P.begin(), P.end());
d.resize(2 * lv + 3);
build(1, 0, lv - 1);
}
void insert(int w, int l, int r, int maxx, int miny, int v) {
if(P[l].X > maxx)
return ;
if(P[r].X <= maxx) {
//~ cout << "ins2d on " << l << " " << r << endl;
d[w]->insert(miny, v);
return ;
}
insert(2 * w, l, (l + r) / 2, maxx, miny, v);
insert(2 * w + 1, (l + r) / 2 + 1, r, maxx, miny, v);
}
int query(int w, int l, int r, ii p) {
if(w >= 2 * lv)
return 0;
if(P[l] > p)
return 0;
if(p > P[r])
return 0;
int res = d[w]->query(p);
res += query(2 * w, l, (l + r) / 2, p);
res += query(2 * w + 1, (l + r) / 2 + 1, r, p);
return res;
}
void insert(int maxx, int miny, int v) {
insert(1, 0, lv - 1, maxx, miny, v);
}
int query(ii p) {
return query(1, 0, lv - 1, p);
}
};
SegmentTree2D *ST;
set<ii> segments;
void init_segments() {
for(int i = 1 ; i <= n ; ) {
int j = i;
while(j <= n && s[j] == '1')
j++;
if(j > i)
segments.insert({i, j - 1});
i = j + 1;
}
}
int query(ii p, int t) {
bool active = false;
auto it = segments.upper_bound({p.X, inf});
if(it != segments.begin()) {
it = prev(it);
auto p2 = *it;
if(p2.Y >= p.Y)
active = true;
}
int v = ST->query(p);
//~ cout << p.X << " " << p.Y << " " << active << " " << v << " " << t << endl;
if(active)
v += t;
return v;
}
void tree_insert(int a, int b, int c, int d, int v) {
//~ cout << "ins" << a << " " << b << " " << c << " " << d << " " << v << endl;
ST->insert(b, c, v);
ST->insert(a - 1, c, -v);
ST->insert(b, d + 1, -v);
ST->insert(a - 1, d + 1, v);
}
void light_up(int i, int t) {
auto rightit = segments.upper_bound((ii){i, inf});
auto leftit = segments.end();
if(rightit != segments.begin())
leftit = prev(rightit);
ii left = {-inf, -inf}, right = {inf, inf};
if(rightit != segments.end()) right = *rightit;
if(leftit != segments.end()) left = *leftit;
if(left.Y == i - 1 && right.X == i + 1) {
tree_insert(left.X, i, i, right.Y, -t);
segments.erase(left);
segments.erase(right);
segments.insert({left.X, right.Y});
} else if(left.Y == i - 1) {
tree_insert(left.X, i, i, i, -t);
segments.erase(left);
segments.insert({left.X, i});
} else if(right.X == i + 1) {
tree_insert(i, i, i, right.Y, -t);
segments.erase(right);
segments.insert({i, right.Y});
} else {
tree_insert(i, i, i, i, -t);
segments.insert({i, i});
}
}
void toggle(int i, int t) {
light_up(i, t);
}
int main() {
scanf("%d%d", &n, &q);
scanf(" %s", s + 1);
for(int i = 0 ; i < q ; i++) {
char comm[10];
scanf(" %s", comm);
if(comm[0] == 't') {
int i;
scanf("%d", &i);
Q.emplace_back(i, -1);
} else {
int a, b;
scanf("%d%d", &a, &b);
Q.emplace_back(a, b);
P.push_back({a, b - 1});
}
}
ST = new SegmentTree2D();
//~ for(auto p : P)
//~ cout << p.X << " " << p.Y << "; " ;
//~ cout << endl;
init_segments();
int t = 1;
for(auto q : Q) {
if(q.Y == -1)
toggle(q.X, t);
else
printf("%d\n", query({q.X, q.Y - 1}, t));
t++;
}
return 0;
}
Compilation message
street_lamps.cpp: In constructor 'SegmentTree2D::SegmentTree2D()':
street_lamps.cpp:86:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(lv < P.size())
~~~^~~~~~~~~~
street_lamps.cpp:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(P.size() < lv)
~~~~~~~~~^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:205:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:206:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", s + 1);
~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:210:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", comm);
~~~~~^~~~~~~~~~~~~
street_lamps.cpp:213:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &i);
~~~~~^~~~~~~~~~
street_lamps.cpp:217:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5097 ms |
144392 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Correct |
7 ms |
504 KB |
Output is correct |
| 3 |
Correct |
8 ms |
760 KB |
Output is correct |
| 4 |
Correct |
8 ms |
760 KB |
Output is correct |
| 5 |
Correct |
868 ms |
8324 KB |
Output is correct |
| 6 |
Correct |
2713 ms |
75356 KB |
Output is correct |
| 7 |
Correct |
3811 ms |
148364 KB |
Output is correct |
| 8 |
Correct |
4898 ms |
296396 KB |
Output is correct |
| 9 |
Incorrect |
4503 ms |
144724 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
760 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
760 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
