#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct Node{
ll s;
int nxt[2];
Node(){
s = 0LL;
nxt[0] = nxt[1] = -1;
}
};
const int MAXN = 3e5 + 7;
const int BASE = (1 << 19);
int vec[MAXN];
vector<Node> tree[2 * BASE + 7];
int n, q;
string napis;
map<pii, int> date;
ll query(int ind, int l, int p, int k, int des){
//cout << ind << ' ' << l << ' ' << p << '\n';
if(l == p){
cout << tree[k][ind].s << '\n';
return tree[k][ind].s;
}
int mid = (l + p) / 2;
ll ret = tree[k][ind].s;
if(des <= mid){
if(tree[k][ind].nxt[0] != -1){
ret += query(tree[k][ind].nxt[0], l, mid, k, des);
}
}else{
if(tree[k][ind].nxt[1] != -1){
ret += query(tree[k][ind].nxt[1], mid + 1, p, k, des);
}
}
return ret;
}
ll getRes(int x, int y){
//cout << "----------\nZAPYTANIE\n";
//cout << x << ' ' << y << '\n';
x += BASE;
ll res = 0;
while(x > 0){
if(sz(tree[x])){
//cout << "----\n";
//cout << x << '\n';
res += query(0, 0, BASE - 1, x, y);
}
x /= 2;
}
return res;
}
void updY(int ind, int l, int p, int a, int b, int val, int k){
if(p < a || b < l){
return;
}
if(a <= l && p <= b){
//cout << "DODAJE: " << k << ' ' << ind << ' ' << val << '\n';
tree[k][ind].s += val;
return;
}
int mid = (l + p) / 2;
if(a <= mid){
if(tree[k][ind].nxt[0] == -1){
tree[k].pb(Node());
tree[k][ind].nxt[0] = sz(tree[k]) - 1;
}
updY(tree[k][ind].nxt[0], l, mid, a, b, val, k);
}
if(b >= mid + 1){
if(tree[k][ind].nxt[1] == -1){
tree[k].pb(Node());
tree[k][ind].nxt[1] = sz(tree[k]) - 1;
}
updY(tree[k][ind].nxt[1], mid + 1, p, a, b, val, k);
}
}
void updX(int v, int l, int p, int a, int b, int val){
if(p < a || b < l){
return;
}
if(a <= l && p <= b){
//zrób dla drugiego wymiaru
if(sz(tree[v]) == 0){
tree[v].pb(Node());
}
updY(0, 0, BASE - 1, a, b, val, v);
return;
}
int mid = (l + p) / 2;
updX(2 * v, l, mid ,a, b, val);
updX(2 * v + 1, mid + 1, p, a, b, val);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
cin >> napis;
for(int i = 0; i < n; i++){
vec[i + 1] = napis[i] - '0';
}
set<pii> s;
int i = 1;
for(i = 1; i <= n; i++){
if(vec[i] == 0){
continue;
}
int pocz = i;
while(i + 1 <= n && vec[i + 1] == 1){
i++;
}
s.insert({pocz, i});
date[{pocz, i}] = 0;
}
for(i = 1; i <= q; i++){
string t;
cin >> t;
// cerr << "NIGGA\n";
if(t == "query"){
int x, y;
cin >> x >> y;
y--;
int ans = 0;
if(vec[x]){
auto it = s.upper_bound({x, 1e9});
it--;
//cout << (*it).fi << ' ' << (*it).se << '\n';
if((*it).se >= y && (*it).fi <= x){
ans += (i - date[*it]);
}
}
//cout << ans << '\n';
ans += getRes(x, y);
cout << ans << '\n';
}else{
int ind;
cin >> ind;
if(vec[ind] == 1){
auto it = s.upper_bound({ind, 1e9});
it--;
// cout << (*it).fi << ' ' << (*it).se << ' ' << i - date[*it] << '\n';
updX(1, 0, BASE - 1, (*it).fi, (*it).se, i - date[*it]);
pii akt = *it;
s.erase(it);
if(ind > akt.fi){
s.insert({akt.fi, ind - 1});
date[{akt.fi, ind - 1}] = i;
}
if(ind < akt.se){
s.insert({ind + 1, akt.se});
date[{ind + 1, akt.se}] = i;
}
}else{
auto it = s.upper_bound({ind, 1e9});
if(!vec[ind - 1] && !vec[ind + 1]){
s.insert({ind, ind});
date[{ind, ind}] = i;
}else if(!vec[ind - 1]){
updX(1, 0, BASE - 1, (*it).fi, (*it).se, i - date[*it]);
pii akt = *it;
s.erase(it);
s.insert({ind, akt.se});
date[{ind, akt.se}] = i;
}else if(!vec[ind + 1]){
it--;
updX(1, 0, BASE - 1, (*it).fi, (*it).se, i - date[*it]);
pii akt = *it;
s.erase(it);
s.insert({akt.fi, ind});
date[{akt.fi, ind}] = i;
}else{
//cerr << "NIGGER\n";
//cerr << (*it).fi << ' ' << (*it).se << '\n';
updX(1, 0, BASE - 1, (*it).fi, (*it).se, i - date[*it]);
pii usu = *it;
it--;
updX(1, 0, BASE - 1, (*it).fi, (*it).se, i - date[*it]);
pii usu2 = *it;
s.erase(usu);
s.erase(usu2);
s.insert({usu2.fi, usu.se});
date[{usu2.fi, usu.se}] = i;
// cout << usu2.fi << ' ' << usu.se << '\n';
}
}
vec[ind] = 1 - vec[ind];
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
24920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
202 ms |
30140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
25688 KB |
Output is correct |
| 2 |
Correct |
12 ms |
25692 KB |
Output is correct |
| 3 |
Correct |
11 ms |
25436 KB |
Output is correct |
| 4 |
Correct |
11 ms |
24924 KB |
Output is correct |
| 5 |
Correct |
1064 ms |
245480 KB |
Output is correct |
| 6 |
Correct |
956 ms |
237032 KB |
Output is correct |
| 7 |
Incorrect |
798 ms |
205968 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
24924 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
25204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
24920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
