#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double
template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
os<<"("<<p.first<<", "<<p.second<<")";
return os;
}
template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
os<<"{";
for(int i = 0;i < (int)v.size(); i++){
if(i)os<<", ";
os<<v[i];
}
os<<"}";
return os;
}
#ifdef LOCAL
#define cerr cout
#else
#endif
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int M = 1.2e7;
template<class T>
struct Data{
int child[2], bits[2], height;
T val;
Data(){
child[0] = bits[0] = child[1] = bits[1] = val = height = 0;
}
};
Data<ll> D[M];
// int child[M][2], bits[M][2], val[M], height[M];
const int MAX_BITS = 31;
int cnt = 0;
inline int clz(int N) {
return N ? 31 - __builtin_clz(N) : -1;
}
template<int num_bits>
struct compressed_trie{
int root;
ll sm;
compressed_trie(){
root = ++cnt;
D[root].height = num_bits;
sm = 0;
}
void add(int x, int v){
sm += v;
int node = root;
int pos = num_bits - 1;
for(; ; ){
Data<ll> & d = D[node];
d.val += v;
if(pos < 0) return;
int dir = x >> pos & 1;
if(!d.child[dir]){
d.child[dir] = ++cnt;
D[cnt].val += v;
d.bits[dir] = x;
return;
}
int y = d.bits[dir];
int nxt = d.child[dir];
int nxtH = D[nxt].height;
y <<= (nxtH);
int diff = clz(x^y);
if(diff < nxtH){
node = nxt;
pos = nxtH - 1;
x &= ((1<<nxtH) - 1);
continue;
}
int yside = y >> diff & 1;
int xside = x >> diff & 1;
d.child[dir] = ++cnt;
d.bits[dir] = x >> (diff + 1);
D[cnt].val = D[nxt].val + v;
D[cnt].height = diff + 1;
D[cnt].child[yside] = nxt;
D[cnt].bits[yside] = (y >> nxtH) & ( (1 << (diff + 1 - nxtH)) - 1);
D[cnt].bits[xside] = x & ((1 << (diff + 1)) - 1);
D[cnt].child[xside] = cnt + 1; ++cnt;
D[cnt].val = v;
return;
}
}
ll order_of_key(int x){
int node = root;
int pos = num_bits - 1;
ll ret = 0;
bool to_print = (x == 11);
for(; pos >= 0; ){
int dir = x >> pos & 1;
Data<ll> & d = D[node];
if(dir) ret += D[d.child[0]].val;
if(!d.child[dir]){
return ret;
}
int y = d.bits[dir];
int nxt = d.child[dir];
int nxtH = D[nxt].height;
y <<= (nxtH);
int diff = clz(x^y);
if(diff < nxtH){
node = nxt;
pos = nxtH - 1;
x &= ((1<<nxtH) - 1);
continue;
}
int xside = x >> diff & 1;
if(xside) ret += D[nxt].val;
return ret;
}
return ret;
}
void insert(int x){
add(x, 1);
}
};
const int N = 300005;
compressed_trie<20> tree[N];
int n, q;
void add(int l, int r, int x, int s = 1, int e = n, int ind = 1){
if(s > l || e < l) return;
tree[ind].add(r, x);
if(s == e) return;
int mid = (s + e) >> 1;
add(l, r, x, s, mid, ind << 1);
add(l, r, x, mid + 1, e, ind << 1 | 1);
}
ll get(int a, int b, int s = 1, int e = n, int ind = 1){
if(s > a) return 0;
if(e <= a) return tree[ind].sm - tree[ind].order_of_key(b);
int mid = (s + e) >> 1;
return get(a, b, s, mid, ind << 1) + get(a, b, mid + 1, e, ind << 1 | 1);
}
set<pair<pii, int>> currIntervals;
char s[N];
int curr[N];
pair<pii, int> get(int p){
auto it = currIntervals.upper_bound({{p + 1, -1}, -1});
it--; return *it;
}
int main(){
sd(n); sd(q);
scanf("%s", s + 1);
for(int i = 1; i <= n; i++) curr[i] = s[i] == '1';
for(int i = 1; i <= n; i++){
if(s[i] == '1'){
int l = i;
while(i <= n && s[i] == '1') i++;
currIntervals.insert({{l, i - 1}, 0});
}
}
for(int t = 1; t <= q; t++){
scanf("%s", s);
if(s[0] == 't'){
int i; sd(i);
if(curr[i]){
auto it = get(i);
int l = it.F.F, r = it.F.S, _t = it.F.S;
add(l, r, t - _t);
currIntervals.erase(it);
if(l <= i - 1) currIntervals.insert({{l, i - 1}, t});
if(r > i) currIntervals.insert({{i + 1, r}, t});
} else{
int x = curr[i - 1], y = curr[i + 1];
int l = i, r = i;
if(x){
auto it = get(i - 1);
l = it.F.F;
add(l, it.F.S, t - it.S);
currIntervals.erase(it);
}
if(y){
auto it = get(i + 1);
r = it.F.S;
add(it.F.F, r, t - it.S);
currIntervals.erase(it);
}
currIntervals.insert({{l, r}, t});
}
curr[i] ^= 1;
} else{
int a, b; sd(a); sd(b); b--;
int ans = get(a, b);
if(curr[a]){
auto it = get(a);
if(it.F.S >= b) ans += t - it.S;
}
printf("%d\n", ans);
}
}
}
Compilation message
street_lamps.cpp: In instantiation of 'long long int compressed_trie<num_bits>::order_of_key(int) [with int num_bits = 20]':
street_lamps.cpp:173:59: required from here
street_lamps.cpp:126:8: warning: unused variable 'to_print' [-Wunused-variable]
bool to_print = (x == 11);
^~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define sd(x) scanf("%d", &(x))
~~~~~^~~~~~~~~~~~
street_lamps.cpp:187:2: note: in expansion of macro 'sd'
sd(n); sd(q);
^~
street_lamps.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define sd(x) scanf("%d", &(x))
~~~~~^~~~~~~~~~~~
street_lamps.cpp:187:9: note: in expansion of macro 'sd'
sd(n); sd(q);
^~
street_lamps.cpp:188: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:198:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s);
~~~~~^~~~~~~~~
street_lamps.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define sd(x) scanf("%d", &(x))
~~~~~^~~~~~~~~~~~
street_lamps.cpp:200:11: note: in expansion of macro 'sd'
int i; sd(i);
^~
street_lamps.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define sd(x) scanf("%d", &(x))
~~~~~^~~~~~~~~~~~
street_lamps.cpp:227:14: note: in expansion of macro 'sd'
int a, b; sd(a); sd(b); b--;
^~
street_lamps.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define sd(x) scanf("%d", &(x))
~~~~~^~~~~~~~~~~~
street_lamps.cpp:227:21: note: in expansion of macro 'sd'
int a, b; sd(a); sd(b); b--;
^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
239 ms |
380796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
491 ms |
385348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
213 ms |
380828 KB |
Output is correct |
| 2 |
Correct |
207 ms |
380792 KB |
Output is correct |
| 3 |
Correct |
208 ms |
380792 KB |
Output is correct |
| 4 |
Correct |
224 ms |
380792 KB |
Output is correct |
| 5 |
Incorrect |
3041 ms |
391288 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
209 ms |
380792 KB |
Output is correct |
| 2 |
Incorrect |
222 ms |
380836 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
239 ms |
380796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
