/** I can do this all day **/
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
ll pw(ll a , ll b, ll M) { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
char C[N];
string s;
int n, q, tp[N], fir[N], sec[N];
vector < int > vec[N], F[2][N]; /// F[0][i] -> sigma -l + r, F[1][i] -> tedad l haye bedune r
set < pii > st;
void pre_add(int i, int r) { for(; i <= n; i += i & -i) { vec[i].push_back(r); } }
void prep()
{
for(int i = 0; i <= n; i ++)
{
vec[i].push_back(-mod);
sort(all(vec[i]));
vec[i].resize(unique(all(vec[i])) - vec[i].begin());
F[0][i].resize(SZ(vec[i]) + 1, 0);
F[1][i].resize(SZ(vec[i]) + 1, 0);
}
}
void pre_ins(int i)
{
if(st.empty()) { st.insert(Mp(i, i)); pre_add(i, i); return; }
auto it = st.lower_bound(Mp(i, 0));
if(it == st.end())
{
it --; pii cu = *it;
if(cu.S == i - 1) { st.erase(it); cu.S ++; st.insert(cu); pre_add(cu.F, cu.S); }
else st.insert(Mp(i, i)), pre_add(i, i);
return;
}
pii R = *it;
if(it == st.begin())
{
if(R.F == i + 1) { st.erase(R); R.F --; st.insert(R); pre_add(R.F, R.S); }
else st.insert(Mp(i, i)), pre_add(i, i);
return;
}
auto it2 = it; it2 --; pii L = *it2;
if(L.S + 1 == R.F - 1) { st.erase(L); st.erase(R); st.insert(Mp(L.F, R.S)); pre_add(L.F, R.S); }
else if(L.S + 1 == i) { st.erase(L); st.insert(Mp(L.F, i)); pre_add(L.F, i); }
else if(R.F == i + 1) { st.erase(R); st.insert(Mp(i, R.S)); pre_add(i, R.S); }
else st.insert(Mp(i, i)), pre_add(i, i);
}
void pre_del(int i)
{
auto it = st.lower_bound(Mp(i, 0));
it --;
pii cu = *it;
st.erase(it);
if(cu.F < i && i < cu.S)
{
st.insert(Mp(cu.F, i - 1)); pre_add(cu.F, i - 1);
st.insert(Mp(i + 1, cu.S)); pre_add(i + 1, cu.S);
}
else if(cu.F == i && i < cu.S) st.insert(Mp(i + 1, cu.S)), pre_add(i + 1, cu.S);
else if(cu.F < i && cu.S == i) st.insert(Mp(cu.F, i - 1)), pre_add(cu.F, i - 1);
}
void add(int i, int r, int Tp, int x)
{
for(; i <= n; i += i & -i)
{
int id = lower_bound(all(vec[i]), r) - vec[i].begin();
for(int j = 1; j < SZ(vec[i]); j += j & -j)
{
F[Tp][i][j] += x;
}
for(int j = id + 1; j < SZ(vec[i]); j += j & -j)
{
F[Tp][i][j] -= x;
}
}
}
ll get(int i, int r, int Tp)
{
ll ret = 0;
for(; i; i -= i & -i)
{
int id = lower_bound(all(vec[i]), r) - vec[i].begin();
for(int j = id; j; j -= j & -j)
{
ret += F[Tp][i][j];
}
}
return ret;
}
inline void _add(int l, int r, int t)
{
add(l, r, 0, -t);
add(l, r, 1, 1);
}
inline void _del(int l, int r, int t)
{
add(l, r, 0, t);
add(l, r, 1, -1);
}
void ins(int i, int t)
{
if(st.empty()) { st.insert(Mp(i, i)); _add(i, i, t); return; }
auto it = st.lower_bound(Mp(i, 0));
if(it == st.end())
{
it --; pii cu = *it;
if(cu.S == i - 1) { st.erase(it); _del(cu.F, cu.S, t); cu.S ++; st.insert(cu); _add(cu.F, cu.S, t); }
else st.insert(Mp(i, i)), _add(i, i, t);
return;
}
pii R = *it;
if(it == st.begin())
{
if(R.F == i + 1) { st.erase(R); _del(R.F, R.S, t); R.F --; st.insert(R); _add(R.F, R.S, t); }
else st.insert(Mp(i, i)), _add(i, i, t);
return;
}
auto it2 = it; it2 --; pii L = *it2;
if(L.S + 1 == R.F - 1) { st.erase(L); _del(L.F, L.S, t); st.erase(R); _del(R.F, R.S, t); st.insert(Mp(L.F, R.S)); _add(L.F, R.S, t); }
else if(L.S + 1 == i) { st.erase(L); _del(L.F, L.S, t); st.insert(Mp(L.F, i)); _add(L.F, i, t); }
else if(R.F == i + 1) { st.erase(R); _del(R.F, R.S, t); st.insert(Mp(i, R.S)); _add(i, R.S, t); }
else st.insert(Mp(i, i)), _add(i, i, t);
}
void del(int i, int t)
{
auto it = st.lower_bound(Mp(i, 0));
it --;
pii cu = *it;
_del(cu.F, cu.S, t);
st.erase(cu);
if(cu.F < i && i < cu.S)
{
st.insert(Mp(cu.F, i - 1)); _add(cu.F, i - 1, t);
st.insert(Mp(i + 1, cu.S)); _add(i + 1, cu.S, t);
}
else if(cu.F == i && i < cu.S) st.insert(Mp(i + 1, cu.S)), _add(i + 1, cu.S, t);
else if(cu.F < i && cu.S == i) st.insert(Mp(cu.F, i - 1)), _add(cu.F, i - 1, t);
}
int main()
{
scanf("%d%d%s", &n, &q, C); s = C; s = "." + s;
string t = s;
set < pii > goshad;
int last = 0;
for(int i = 1; i <= n; i ++)
{
if(s[i] == '0')
{
if(last == i - 1) { last = i; continue; }
pre_add(last + 1, i - 1); st.insert(Mp(last + 1, i - 1)); goshad.insert(Mp(last + 1, i - 1));
last = i;
}
}
if(last != n) { pre_add(last + 1, n); st.insert(Mp(last + 1, n)); goshad.insert(Mp(last + 1, n)); }
for(int i = 1; i <= q; i ++)
{
scanf("%s%d", C, &fir[i]);
if(C[0] == 't') tp[i] = 1;
else tp[i] = 2, scanf("%d", &sec[i]), sec[i] --;
if(tp[i] == 1)
{
if(s[fir[i]] == '0') pre_ins(fir[i]);
else pre_del(fir[i]);
}
else
{
pre_add(fir[i], sec[i]);
}
}
prep();
st = goshad;
for(auto x : st)
{
_add(x.F, x.S, 0);
}
s = t;
for(int i = 1; i <= q; i ++)
{
if(tp[i] == 1)
{
if(s[fir[i]] == '0')
{
ins(fir[i], i);
}
else
{
del(fir[i], i);
}
}
else
{
ll tot = 1ll * i * get(fir[i], sec[i], 1) + get(fir[i], sec[i], 0);
printf("%lld\n", tot);
}
}
return 0;
}
/** tesy corner cases(n = 1?) watch for overflow or minus indices **/
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
178 | scanf("%d%d%s", &n, &q, C); s = C; s = "." + s;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:194:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
194 | scanf("%s%d", C, &fir[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:196:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
196 | else tp[i] = 2, scanf("%d", &sec[i]), sec[i] --;
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
140 ms |
143532 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
138 ms |
143340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
71020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
71020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
140 ms |
143532 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
