#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;
const int len = 3e5+5;
set<ii> mys;
int light[len]; // n_len
struct seg_tree{
int mx;
vector<pair<int, ii> > vec;
seg_tree(int m = 0){
mx = m;
}
void upd(int y, int sum, int num){
vec.pb(mp(y, mp(sum, num)));
}
ii ask(int y_){
int sum_ = 0, num_ = 0;
for (int j = 0; j < vec.size(); j++){
int y = vec[j].fi, sum = vec[j].se.fi, num = vec[j].se.se;
if (y >= y_)
sum_ += sum, num_ += num;
}
return mp(sum_, num_);
}
};
struct bit{
seg_tree tree[len];
int mx;
bit(int r = 0, int c = 0){
mx = r;
for (int i = 1; i <= r; i++)
tree[i] = seg_tree(c);
}
void upd(int x, int y, int sum, int num){
while (x <= mx)
tree[x].upd(y, sum, num), x += x&(-x);
}
int ask(int x, int y, int tim){
int sum = 0, num = 0;
while (x > 0){
sum += tree[x].ask(y).fi;
num += tree[x].ask(y).se;
x -= x&(-x);
}
return sum + num*tim;
}
};
bit data;
ii rig(int i){
auto it = mys.lower_bound(mp(i, 0));
if (it == mys.end())
return mp(-1, -1);
return *it;
}
ii lef(int i){
auto it = mys.lower_bound(mp(i+1, 0));
if (it == mys.begin())
return mp(-1, -1);
return *(--it);
}
void print(){
printf("current intervals:");
for (auto it: mys)
printf(" (%d, %d)", it.fi, it.se);
printf("\n");
}
void toggle(int i, int t = 0){
light[i] ^= 1;
if (light[i] == 1){
ii cur = mp(i, i), l = lef(i-1), r = rig(i+1);
if (l.se+1 == cur.fi){
// remove l and update data and extend cur
mys.erase(l);
data.upd(l.fi, l.se, +t, -1);
cur.fi = l.fi;
}
if (cur.se == r.fi-1){
// remove r and update data and extend cur
mys.erase(r);
data.upd(r.fi, r.se, +t, -1);
cur.se = r.se;
}
// insert cur and update data
mys.insert(cur);
data.upd(cur.fi, cur.se, -t, +1);
}
else{
ii cur = lef(i), l = mp(cur.fi, i-1), r = mp(i+1, cur.se);
// remove cur and update data
mys.erase(cur);
data.upd(cur.fi, cur.se, +t, -1);
if (l.fi <= l.se){
// insert l and update data
mys.insert(l);
data.upd(l.fi, l.se, -t, +1);
}
if (r.fi <= r.se){
// insert r and update data
mys.insert(r);
data.upd(r.fi, r.se, -t, +1);
}
}
//print();
}
int main(){
int n, q;
scanf("%d %d ", &n, &q);
data = bit(n, n);
for (int i = 1; i <= n; i++){
char temp;
scanf("%c", &temp);
if (temp == '1')
toggle(i);
}
for (int i = 1; i <= q; i++){
char str[15];
scanf("%s", str);
if (str[0] == 'q'){
int a, b;
scanf("%d %d", &a, &b);
b--;
printf("%d\n", data.ask(a, b, i));
//printf("asked for interval (%d, %d)\n", a, b);
}
else{
int pos;
scanf("%d", &pos);
toggle(pos, i);
}
//printf("%d) ", i);
//print();
}
return 0;
}
Compilation message
street_lamps.cpp: In member function 'ii seg_tree::ask(int)':
street_lamps.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (int j = 0; j < vec.size(); j++){
| ~~^~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
132 | scanf("%d %d ", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:138:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
138 | scanf("%c", &temp);
| ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:145:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
145 | scanf("%s", str);
| ~~~~~^~~~~~~~~~~
street_lamps.cpp:148:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
148 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:156:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
156 | scanf("%d", &pos);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
19072 KB |
Output is correct |
| 2 |
Correct |
15 ms |
19200 KB |
Output is correct |
| 3 |
Correct |
16 ms |
19072 KB |
Output is correct |
| 4 |
Correct |
15 ms |
19072 KB |
Output is correct |
| 5 |
Correct |
14 ms |
19072 KB |
Output is correct |
| 6 |
Correct |
14 ms |
19104 KB |
Output is correct |
| 7 |
Correct |
17 ms |
19072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5054 ms |
27696 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
19328 KB |
Output is correct |
| 2 |
Correct |
17 ms |
19328 KB |
Output is correct |
| 3 |
Correct |
21 ms |
19328 KB |
Output is correct |
| 4 |
Correct |
20 ms |
19328 KB |
Output is correct |
| 5 |
Correct |
1605 ms |
121280 KB |
Output is correct |
| 6 |
Execution timed out |
5049 ms |
63936 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
19200 KB |
Output is correct |
| 2 |
Correct |
16 ms |
19232 KB |
Output is correct |
| 3 |
Correct |
16 ms |
19328 KB |
Output is correct |
| 4 |
Correct |
17 ms |
19456 KB |
Output is correct |
| 5 |
Execution timed out |
5010 ms |
58956 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
19072 KB |
Output is correct |
| 2 |
Correct |
15 ms |
19200 KB |
Output is correct |
| 3 |
Correct |
16 ms |
19072 KB |
Output is correct |
| 4 |
Correct |
15 ms |
19072 KB |
Output is correct |
| 5 |
Correct |
14 ms |
19072 KB |
Output is correct |
| 6 |
Correct |
14 ms |
19104 KB |
Output is correct |
| 7 |
Correct |
17 ms |
19072 KB |
Output is correct |
| 8 |
Execution timed out |
5054 ms |
27696 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
