#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
struct upd{
int l, r, fr, to;
};
struct line{
int l, r, x;
};
namespace bit2d{
vector<int> solve(vector<upd> U, vector<line> Q){
vector<int> ans(Q.size());
for(int i = 0; i < U.size(); i++){
for(int j = 0; j < Q.size(); j++){
if(U[i].l <= Q[j].l && Q[j].r <= U[i].r && U[i].fr <= Q[j].x)
ans[j] += min(Q[j].x, U[i].to) - U[i].fr;
}
}
return ans;
}
};
namespace gen_upd{
struct range{
int l, r, t;
bool operator< (const range& o) const {
return l < o.l;
}
};
set<range> s; vector<bool> u;
vector<upd> U;
void init(string _s){
u.resize(_s.size());
for(int i = 0; i < _s.size(); i++) u[i] = _s[i] - '0';
int l = 0, r = 0;
for(int i = 0; i < _s.size(); i++){
if(_s[i] == '1'){
r = i + 1;
}else{
s.insert({l, r, 0});
l = i + 1;
}
}
s.insert({l, _s.size(), 0});
}
void add(int t, int x){
if(u[x]){
auto ptr = s.lower_bound({x + 1, 0}); --ptr;
U.push_back({ptr->l, ptr->r, ptr->t, t});
s.insert({ptr->l, x, t});
s.insert({x + 1, ptr->r, t});
}else{
int l = x, r = x + 1;
auto ptr = s.lower_bound({x + 1, 0});
if(ptr != s.end() && ptr->l == x + 1){
U.push_back({ptr->l, ptr->r, ptr->t, t});
r = ptr->r; s.erase(ptr);
}
ptr = s.upper_bound({x, 0});
if(ptr != s.begin() && prev(ptr)->r == x){
ptr--;
U.push_back({ptr->l, prev(ptr)->r, ptr->t, t});
l = ptr->l; s.erase(ptr);
}
s.insert({l, r, t});
}
u[x] = !u[x];
}
void final(int t){
for(auto i : s){
U.push_back({i.l, i.r, i.t, t});
}
}
};
int main(){
int n, q; cin >> n >> q; string s; cin >> s; gen_upd::init(s);
vector<upd> U; vector<line> Q;
for(int t = 1; t <= q; t++){
string ty; cin >> ty;
if(ty == "toggle"){
int x; cin >> x; x--; gen_upd::add(t, x);
}else{
int ql, qr; cin >> ql >> qr; ql--; qr--; Q.push_back({ql, qr, t});
}
}
gen_upd::final(q); U = gen_upd::U;
vector<int> ans = bit2d::solve(U, Q);
for(auto a : ans){
cout << a << ' ';
}
cout << endl;
}
Compilation message
street_lamps.cpp: In function 'std::vector<int> bit2d::solve(std::vector<upd>, std::vector<line>)':
street_lamps.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i = 0; i < U.size(); i++){
| ~~^~~~~~~~~~
street_lamps.cpp:19:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int j = 0; j < Q.size(); j++){
| ~~^~~~~~~~~~
street_lamps.cpp: In function 'void gen_upd::init(std::string)':
street_lamps.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i = 0; i < _s.size(); i++) u[i] = _s[i] - '0';
| ~~^~~~~~~~~~~
street_lamps.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i = 0; i < _s.size(); i++){
| ~~^~~~~~~~~~~
street_lamps.cpp:50:23: warning: narrowing conversion of '_s.std::__cxx11::basic_string<char>::size()' from 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
50 | s.insert({l, _s.size(), 0});
| ~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5089 ms |
13224 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
