This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
void debug_out()
{
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B)
{
cerr << ' ' << A;
debug_out(B...);
}
#ifdef DEBUG
#define time(...) 42
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
const int maxN = 300005;
char a0[maxN];
pii que[maxN];
signed main()
{
#ifdef DEBUG
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
if (n <= 100 && q <= 100)
{
char t[q + 1][n];
memset(t, 0, sizeof(t));
string s;
cin >> s;
for (int i = 0; i < n; ++i) t[0][i] = s[i] - '0';
for (int i = 1; i <= q; ++i)
{
memcpy(t[i], t[i - 1], sizeof(t[i]));
string cmd;
cin >> cmd;
if (cmd == "toggle")
{
int j;
cin >> j;
--j;
t[i][j] ^= 1;
}
else
{
int l, r;
cin >> l >> r;
r -= 2;
l--;
int ans = 0;
for (int u = 0; u < i; ++u)
{
bool ok = true;
for (int j = l; j <= r; ++j)
{
ok &= t[u][j];
}
if (ok) ++ans;
}
cout << ans << '\n';
}
}
exit(0);
}
// normal
string tmp;
cin >> tmp;
for (int i = 0; i < n; ++i) a0[i] = tmp[i] - '0';
bool all_ones = true;
bool toggle_to_one = true;
int _a[n];
for (int i = 0; i < n; ++i) _a[i] = a0[i];
for (int t = 1; t <= q; ++t)
{
string cmd;
cin >> cmd;
auto &q = que[t];
if (cmd == "toggle")
{
q.se = -1;
cin >> q.fi;
q.fi--;
int i = q.fi;
_a[i] ^= 1;
toggle_to_one &= _a[i] == 1;
}
else
{
cin >> q.fi >> q.se;
q.fi--;
q.se -= 2;
all_ones &= q.fi == q.se;
}
}
if (all_ones)
{
int when[n], sum[n];
memset(when, 0, sizeof(when));
memset(sum, 0, sizeof(sum));
for (int t = 1; t <= q; ++t)
{
auto &q = que[t];
if (q.se == -1)
{
int i = q.fi;
if (a0[i] == 0)
{
when[i] = t;
}
else
{
sum[i] += t - when[i];
}
a0[i] ^= 1;
}
else
{
int i = q.fi;
cout << sum[i] + (a0[i] == 1 ? t - when[i] : 0) << '\n';
}
}
exit(0);
}
if (toggle_to_one)
{
int when[n];
memset(when, 0x3f, sizeof(when));
for (int t = 1; t <= q; ++t)
{
auto &q = que[t];
if (q.se == -1)
{
int i = q.fi;
when[i] = t;
}
}
const int logN = 19;
const int N = 1 << logN;
int sgt[2 * N];
memset(sgt, 0x3f, sizeof(sgt));
for (int i = 0; i < n; ++i)
{
sgt[i + N] = when[i];
}
for (int v = N - 1; v >= 1; --v)
{
sgt[v] = max(sgt[v << 1], sgt[v << 1 | 1]);
}
for (int t = 1; t <= q; ++t)
{
auto &q = que[t];
if (q.se != -1)
{
int l = q.fi;
int r = q.se;
int mx = -1e9;
for (int L = l, R = r; L <= R; L >>= 1, R >>= 1)
{
if (L & 1) chkmax(mx, sgt[L++]);
if (!R & 1) chkmax(mx, sgt[R--]);
}
cout << max(0, t - mx) << '\n';
}
}
exit(0);
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |