#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct interval
{
int left, right, in_time;
interval(int _left, int _right, int _in_time)
{
left = _left;
right = _right;
in_time = _in_time;
}
bool operator < (const interval &it) const
{
return left < it.left;
}
};
const int maxn = 3e5 + 10;
struct base_query
{
string type;
int x, a, b;
} base_ask[maxn];
int n, q;
char c[maxn], cs[maxn];
void input()
{
cin >> n >> q;
n ++;
for (int i = 1; i < n; i ++)
cin >> c[i], cs[i] = c[i];
for (int i = 1; i <= q; i ++)
{
cin >> base_ask[i].type;
if (base_ask[i].type == "query")
{
cin >> base_ask[i].a >> base_ask[i].b;
}
else
{
cin >> base_ask[i].x;
}
}
}
set < pair < int, int > > available;
void create_intervals()
{
set < interval > st;
int beg = 1;
for (int i = 1; i < n; i ++)
{
if (c[i] == '0')
{
///cout << beg << " -- " << i << endl;
st.insert(interval(beg, i, 0));
available.insert({beg, i});
beg = i + 1;
}
}
st.insert(interval(beg, n, 0));
available.insert({beg, n});
for (int i = 1; i <= q; i ++)
{
if (base_ask[i].type == "toggle")
{
int pos = base_ask[i].x;
if (c[pos] == '0')
{
c[pos] = '1';
set < interval > :: iterator aft_it = st.lower_bound(interval(pos + 1, pos + 1, -1));
set < interval > :: iterator bef_it = prev(aft_it);
interval bef = *bef_it;
interval aft = *aft_it;
interval cur(bef.left, aft.right, i);
st.erase(bef);
st.erase(aft);
st.insert(cur);
available.insert({cur.left, cur.right});
}
else
{
c[pos] = '0';
set < interval > :: iterator cur_it = prev(st.lower_bound(interval(pos + 1, pos + 1, -1)));
interval cur = *cur_it;
interval bef(cur.left, pos, i);
interval aft(pos, cur.right, i);
st.erase(cur);
st.insert(bef);
st.insert(aft);
available.insert({bef.left, bef.right});
available.insert({aft.left, aft.right});
}
}
}
//for (pair < int, int > cur : available)
// cout << cur.first << " : " << cur.second << endl;
}
const int smalln = 110;
int act[smalln][smalln], act_time[smalln][smalln], sum[smalln][smalln];
void update_interval(interval cur, int cur_time)
{
///cout << "update " << cur.left << " " << cur.right << endl;
if (act[cur.left][cur.right])
{
act[cur.left][cur.right] = 0;
sum[cur.left][cur.right] += cur_time - act_time[cur.left][cur.right];
}
else
{
act_time[cur.left][cur.right] = cur_time;
act[cur.left][cur.right] = 1;
}
}
void simulate()
{
set < interval > st;
int beg = 1;
for (int i = 1; i < n; i ++)
{
c[i] = cs[i];
if (c[i] == '0')
{
st.insert(interval(beg, i, 0));
act[beg][i] = 1;
act_time[beg][i] = 0;
beg = i + 1;
}
}
act[beg][n] = 1;
st.insert(interval(beg, n, 0));
for (int i = 1; i <= q; i ++)
{
if (base_ask[i].type == "toggle")
{
///cout << "toggle" << endl;
int pos = base_ask[i].x;
if (c[pos] == '0')
{
c[pos] = '1';
set < interval > :: iterator aft_it = st.lower_bound(interval(pos + 1, pos + 1, -1));
set < interval > :: iterator bef_it = prev(aft_it);
interval bef = *bef_it;
interval aft = *aft_it;
interval cur(bef.left, aft.right, i);
update_interval(bef, i);
update_interval(aft, i);
update_interval(cur, i);
st.erase(bef);
st.erase(aft);
st.insert(cur);
available.insert({cur.left, cur.right});
}
else
{
c[pos] = '0';
set < interval > :: iterator cur_it = prev(st.lower_bound(interval(pos + 1, pos + 1, -1)));
interval cur = *cur_it;
interval bef(cur.left, pos, i);
interval aft(pos + 1, cur.right, i);
///cout << " ::: " << bef.left << " " << bef.right << endl;
st.erase(cur);
st.insert(bef);
st.insert(aft);
update_interval(bef, i);
update_interval(aft, i);
update_interval(cur, i);
available.insert({bef.left, bef.right});
available.insert({aft.left, aft.right});
}
}
else
{
ll ans = 0;
for (int l = 1; l <= base_ask[i].a; l ++)
for (int r = base_ask[i].b; r <= n; r ++)
{
ans = ans + sum[l][r];
///cout << l << " -- " << r << " " << act[l][r] << endl;
if (act[l][r])
{
///cout << l << " " << r << endl;
ans = ans + i - act_time[l][r];
}
}
cout << ans << endl;
}
}
//for (pair < int, int > cur : available)
// cout << cur.first << " : " << cur.second << endl;
}
void solve()
{
input();
create_intervals();
simulate();
}
int main()
{
solve();
return 0;
}
/**
5 3
11011
toggle 2
toggle 1
query 1 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14400 KB |
Output is correct |
| 3 |
Correct |
9 ms |
14344 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14548 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14548 KB |
Output is correct |
| 6 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
8 ms |
14360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
641 ms |
16328 KB |
Output is correct |
| 2 |
Runtime error |
1252 ms |
35568 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
15036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
14944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14400 KB |
Output is correct |
| 3 |
Correct |
9 ms |
14344 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14548 KB |
Output is correct |
| 5 |
Correct |
7 ms |
14548 KB |
Output is correct |
| 6 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 7 |
Correct |
8 ms |
14360 KB |
Output is correct |
| 8 |
Correct |
641 ms |
16328 KB |
Output is correct |
| 9 |
Runtime error |
1252 ms |
35568 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
