#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair
struct str{ //half open
vector<pair<int,int>> v;
str marge(str s){
vector<pair<int,int>> tmp;
for(int i=0; i<v.size(); i++) tmp.push_back(v[i]);
for(int i=0; i<s.v.size(); i++) tmp.push_back(s.v[i]);
sort(tmp.begin(), tmp.end());
str ret;
for(int i=0; i+1<tmp.size(); i++){
if(tmp[i+1].first <= tmp[i].second-1){
ret.v.push_back(MP(tmp[i+1].first, tmp[i].second));
}
}
return ret;
}
};
int N,Q;
string def;
int t[300000],a[300000],b[300000];
vector<int> toggle[300000];
int ans[300000] = {};
str seg[1200000] = {};
int seg_size = 1;
str full;
str query(int a, int b, int k=0, int l=0, int r=-1){
if(r == -1) r = seg_size;
if(r <= a || b <= l) return full;
if(a <= l && r <= b) return seg[k];
return query(a, b, 2*k+1, l, (l+r)/2).marge(query(a, b, 2*k+2, (l+r)/2, r));
}
int main(){
cin >> N >> Q;
cin >> def;
for(int i=0; i<N; i++){
if(def[i] == '1') toggle[i].push_back(0);
}
for(int i=0; i<Q; i++){
string type;
cin >> type;
if(type == "toggle"){
t[i] = 0;
cin >> a[i];
a[i]--;
toggle[a[i]].push_back(i+1);
}
else{
t[i] = 1;
cin >> a[i] >> b[i];
a[i]--; b[i]--;
}
}
vector<pair<int,int>> d;
while(seg_size < N) seg_size *= 2;
for(int i=0; i<seg_size*2-1; i++) seg[i].v = d;
for(int i=0; i<N; i++){
str tmp;
for(int j=0; j+1<toggle[i].size(); j+=2){
tmp.v.push_back(MP(toggle[i][j], toggle[i][j+1]));
}
if(toggle[i].size()%2 == 1){
tmp.v.push_back(MP(toggle[i].back(), N+1));
}
seg[seg_size-1+i] = tmp;
}
for(int i=seg_size-2; i>=0; i--){
seg[i] = seg[2*i+1].marge(seg[2*i+2]);
}
full.v.push_back(MP(0, N+1));
for(int i=0; i<Q; i++){
if(t[i] == 1){
str ans = query(a[i], b[i]);
int ret = 0;
for(int j=0; j<ans.v.size(); j++){
if(ans.v[j].first >= i+1) break;
if(ans.v[i].second >= i+1) ret += i+1 - ans.v[j].first;
else ret += ans.v[j].second - ans.v[j].first;
cout << ans.v[i].first << " " << ans.v[i].second << endl;
}
cout << ret << endl;
}
}
return 0;
}
Compilation message
street_lamps.cpp: In member function 'str str::marge(str)':
street_lamps.cpp:10:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++) tmp.push_back(v[i]);
~^~~~~~~~~
street_lamps.cpp:11:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<s.v.size(); i++) tmp.push_back(s.v[i]);
~^~~~~~~~~~~
street_lamps.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i+1<tmp.size(); i++){
~~~^~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j+1<toggle[i].size(); j+=2){
~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<ans.v.size(); j++){
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
35576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5055 ms |
42560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
35704 KB |
Output is correct |
| 2 |
Incorrect |
38 ms |
35704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
35576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
35576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
