#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define y1 orz
#define y2 tmw
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define MAXN 351313
#define INF 1000000007
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, Q;
bitset<MAXN> state;
pii quer[MAXN];
unordered_map<int, ll> fen[MAXN];
int lst[MAXN];
set<int> lts, rts;
int ans;
void upd(int x, int y, int val)
{
for (int e = x + 1; e <= N; e += e & (-e))
{
for (int f = y + 1; f <= N; f += f & (-f))
{
fen[e][f] += val;
}
}
}
ll qry(int x, int y)
{
ll res = 0;
for (int e = x + 1; e; e -= e & (-e))
{
for (int f = y + 1; f; f -= f & (-f))
{
auto it = fen[e].find(f);
if (it != fen[e].end())
{
res += it -> se;
}
}
}
return res;
}
void del(int idx, int t)
{
int lt = *prev(lts.UB(idx)), rt = *rts.LB(idx);
lts.erase(lt); rts.erase(rt);
upd(lt, N - 1 - rt, t - lst[lt]);
if (lt != idx)
{
lst[lt] = t;
lts.insert(lt);
rts.insert(idx - 1);
}
if (rt != idx)
{
lst[idx + 1] = t;
lts.insert(idx + 1);
rts.insert(rt);
}
}
void ins(int idx, int t)
{
if (rts.find(idx - 1) != rts.end() && lts.find(idx + 1) != lts.end())
{
int lt = *prev(lts.UB(idx)), rt = *rts.LB(idx);
rts.erase(idx - 1);
lts.erase(idx + 1);
upd(lt, N - idx, t - lst[lt]);
upd(idx + 1, N - 1 - rt, t - lst[idx + 1]);
lst[lt] = t;
}
else if (rts.find(idx - 1) != rts.end())
{
int lt = *prev(lts.UB(idx));
rts.erase(idx - 1);
rts.insert(idx);
upd(lt, N - idx, t - lst[lt]);
lst[lt] = t;
}
else if (lts.find(idx + 1) != lts.end())
{
int rt = *rts.LB(idx);
lts.erase(idx + 1);
lts.insert(idx);
upd(idx + 1, N - 1 - rt, t - lst[idx + 1]);
lst[idx] = t;
}
else
{
lts.insert(idx);
rts.insert(idx);
lst[idx] = t;
}
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(12);
cerr << fixed << setprecision(4);
cin >> N >> Q;
string temps; cin >> temps;
FOR(i, 0, N)
{
state[i] = (temps[i] == '1');
}
FOR(i, 0, N)
{
if (state[i] && (i == 0 || !state[i - 1])) lts.insert(i);
if (state[i] && (i == N - 1 || !state[i + 1])) rts.insert(i);
}
for (auto it = lts.begin(); it != lts.end(); it++)
{
lst[*it] = -1;
}
FOR(i, 0, Q)
{
cin >> temps;
int x, y;
if (temps[0] == 't')
{
cin >> x; x--;
quer[i] = {-1, x};
}
else
{
cin >> x >> y; x--; y -= 2;
quer[i] = {x, y};
}
}
lts.clear(); rts.clear();
FOR(i, 0, N)
{
if (state[i] && (i == 0 || !state[i - 1])) lts.insert(i);
if (state[i] && (i == N - 1 || !state[i + 1])) rts.insert(i);
}
FOR(i, 0, Q)
{
if (quer[i].fi == -1)
{
int idx = quer[i].se;
if (!state[idx])
{
ins(idx, i);
}
else
{
del(idx, i);
}
state[idx] = state[idx] ^ 1;
}
else
{
int lt = quer[i].fi, rt = quer[i].se;
ans = qry(lt, N - 1 - rt);
auto it = rts.LB(rt);
if (it != rts.end())
{
auto jt = prev(lts.UB(*it));
if (*jt <= lt)
{
int t = lst[*jt];
ans += (i - t);
}
}
cout << ans << '\n';
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
19576 KB |
Output is correct |
2 |
Correct |
20 ms |
19576 KB |
Output is correct |
3 |
Correct |
20 ms |
19576 KB |
Output is correct |
4 |
Correct |
21 ms |
19540 KB |
Output is correct |
5 |
Correct |
20 ms |
19576 KB |
Output is correct |
6 |
Correct |
20 ms |
19576 KB |
Output is correct |
7 |
Correct |
20 ms |
19576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
276 ms |
23056 KB |
Output is correct |
2 |
Correct |
376 ms |
23252 KB |
Output is correct |
3 |
Correct |
1004 ms |
27128 KB |
Output is correct |
4 |
Correct |
4807 ms |
156728 KB |
Output is correct |
5 |
Execution timed out |
5085 ms |
170504 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
19960 KB |
Output is correct |
2 |
Correct |
25 ms |
19912 KB |
Output is correct |
3 |
Correct |
31 ms |
19960 KB |
Output is correct |
4 |
Correct |
24 ms |
19576 KB |
Output is correct |
5 |
Execution timed out |
5024 ms |
207412 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
19704 KB |
Output is correct |
2 |
Correct |
22 ms |
19832 KB |
Output is correct |
3 |
Correct |
23 ms |
19920 KB |
Output is correct |
4 |
Correct |
23 ms |
19984 KB |
Output is correct |
5 |
Correct |
1914 ms |
38428 KB |
Output is correct |
6 |
Correct |
4292 ms |
129088 KB |
Output is correct |
7 |
Execution timed out |
5049 ms |
166628 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
19576 KB |
Output is correct |
2 |
Correct |
20 ms |
19576 KB |
Output is correct |
3 |
Correct |
20 ms |
19576 KB |
Output is correct |
4 |
Correct |
21 ms |
19540 KB |
Output is correct |
5 |
Correct |
20 ms |
19576 KB |
Output is correct |
6 |
Correct |
20 ms |
19576 KB |
Output is correct |
7 |
Correct |
20 ms |
19576 KB |
Output is correct |
8 |
Correct |
276 ms |
23056 KB |
Output is correct |
9 |
Correct |
376 ms |
23252 KB |
Output is correct |
10 |
Correct |
1004 ms |
27128 KB |
Output is correct |
11 |
Correct |
4807 ms |
156728 KB |
Output is correct |
12 |
Execution timed out |
5085 ms |
170504 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |