#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl; g(...) 0
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
b%=m;
ll ans = 1;
for (; e; b = b * b % m, e /= 2)
if (e & 1) ans = ans * b % m;
return ans;
}
template<class T, int SZ> struct OffBIT2D {
bool mode = 0; // mode = 1 -> initialized
vector<pii> todo; // locations of updates to process
int cnt[SZ], st[SZ];
vi val; vector<T> bit; // store all BITs in single vector
void init() { assert(!mode); mode = 1;
int lst[SZ];
rep(i,0,SZ) lst[i] = cnt[i] = 0;
sort(all(todo),[](const pii& a, const pii& b) {
return a.ss < b.ss; });
trav(t,todo) for (int x = t.ff; x < SZ; x += x&-x) {
if (lst[x] != t.ss) lst[x] = t.ss, cnt[x] ++;
}
int sum = 0; rep(i,0,SZ) lst[i] = 0, st[i] = (sum += cnt[i]);
val.resize(sum); bit.resize(sum); reverse(all(todo));
trav(t,todo) for (int x = t.ff; x < SZ; x += x&-x)
if (lst[x] != t.ss) lst[x] = t.ss, val[--st[x]] = t.ss;
}
int rank(int y, int l, int r) {
return upper_bound(begin(val)+l,begin(val)+r,y)-begin(val)-l; }
void UPD(int x, int y, T t) {
for (y = rank(y,st[x],st[x]+cnt[x]); y <= cnt[x]; y += y&-y)
bit[st[x]+y-1] += t; }
void upd(int x, int y, T t) {
if (!mode) todo.pb({x,y});
else for (;x<SZ;x+=x&-x) UPD(x,y,t); }
int QUERY(int x, int y) { T res = 0;
for (y = rank(y,st[x],st[x]+cnt[x]); y; y -= y&-y) res += bit[st[x]+y-1];
return res; }
T query(int x, int y) { assert(mode);
T res = 0; for (;x;x-=x&-x) res += QUERY(x,y);
return res; }
T query(int xl, int xr, int yl, int yr) {
return query(xr,yr)-query(xl-1,yr)
-query(xr,yl-1)+query(xl-1,yl-1); }
};
struct event{
int l,r,mx,v;
};
OffBIT2D<ll,300100> BIT;
vector<event> ev;
int n,q;
void add_event(int l,int r,int mx,ll v,int A=0){
BIT.upd(l,mx,v);
if(r!=n)BIT.upd(r+1,mx,-v);
if(!A)ev.pb({l,r,mx,v});
}
ll ask(int a,int b,int A=0){
ll res=0;
if(!A)ev.pb({a,b,-1,-1});
else{
res = BIT.query(1,a,b,n);
}
return res;
}
const int N = 300100;
char s[N];
int fim[N];
int last[N];
string Q[N];
int a[N],b[N];
int32_t main(){
fastio;
cin >> n >> q;
for(int i=1;i<=n;i++){
cin >> s[i];
}
s[0]='0';
set<pii> S;
for(int i=n;i>=0;i--){
if(s[i]=='1' and s[i+1]=='1')fim[i] = fim[i+1];
else if(s[i]=='1'){
fim[i] = i;
}
if(s[i] == '0' and s[i+1]=='1'){
S.insert(pii(i+1,fim[i+1]));
}
last[i] = 0;
}
for(int i=1;i<=q;i++){
cin >> Q[i];
if(Q[i][0]=='t'){
cin >> a[i];
int pos = a[i];
if(s[pos] == '0'){
s[pos] ='1';
int l = pos,r = pos;
if(s[pos-1]=='1'){
auto it = S.lower_bound(pii(pos,-1));
assert(it!=S.begin());
it--;
l = it->ff;
add_event(it->ff,it->ss,it->ss,i-last[it->ff]);
last[it->ff] = i;
S.erase(it);
}
if(s[pos+1]=='1'){
auto it = S.lower_bound(pii(pos,-1));
assert(it!=S.end());
r=it->ss;
add_event(it->ff,it->ss,it->ss,i-last[it->ff]);
last[it->ff] = i;
S.erase(it);
}
S.insert(pii(l,r));
last[l] = i;
// db2(l,r);
}else{
s[pos]='1';
auto it = S.lower_bound(pii(i+1,-1));
assert(it!=S.begin());
it--;
int t = last[it->ff];
int l = it->ff,r = it->ss;
if(pos!=r)
last[pos+1] = t;
add_event(l,pos,it->ss,i-last[it->ff]);
last[l] = i;
if(pos!=l)S.insert(pii(l,pos-1));
if(pos!=r)S.insert(pii(pos+1,r));
}
}else{
cin >> a[i] >> b[i];
b[i]--;
if(s[a[i]] == '0'){
ask(a[i],b[i]);
// cout << "HI "<<a[i] << endl;
continue;
}
auto it = S.lower_bound(pii(a[i]+1,-1));
assert(it!=S.begin());
it--;
add_event(it->ff,it->ss,it->ss,i-last[it->ff]);
//cout << "HI "<<it->ff<<" "<<it->ss<<" "<<last[it->ff] << endl;
last[it->ff] = i;
ask(a[i],b[i]);
}
}
BIT.init();
for(auto it : ev){
//cout << it.l<<" "<<it.r<<" "<<it.mx<<" "<<it.v << endl;
if(it.mx != -1){
add_event(it.l,it.r,it.mx,it.v,1);
}else{
cout << ask(it.l,it.r,1) << endl;
}
}
// math -> gcd it all
// Did u check N=1? Did you switch N,M?
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
353 ms |
91144 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
17132 KB |
Output is correct |
| 2 |
Correct |
13 ms |
17284 KB |
Output is correct |
| 3 |
Correct |
13 ms |
17132 KB |
Output is correct |
| 4 |
Correct |
12 ms |
17004 KB |
Output is correct |
| 5 |
Correct |
1371 ms |
85012 KB |
Output is correct |
| 6 |
Correct |
1614 ms |
88148 KB |
Output is correct |
| 7 |
Correct |
1650 ms |
83844 KB |
Output is correct |
| 8 |
Correct |
315 ms |
69432 KB |
Output is correct |
| 9 |
Correct |
314 ms |
52880 KB |
Output is correct |
| 10 |
Correct |
327 ms |
53752 KB |
Output is correct |
| 11 |
Correct |
323 ms |
57004 KB |
Output is correct |
| 12 |
Correct |
177 ms |
40252 KB |
Output is correct |
| 13 |
Correct |
300 ms |
69432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
17004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
