#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 INF32 = 1e9;
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];
for (int i = 0; i < n; ++i)
if (a0[i] == 1)
when[i] = 0;
else
when[i] = INF32;
for (int t = 1; t <= q; ++t)
{
auto &q = que[t];
if (q.se == -1)
{
int i = q.fi;
when[i] = t;
}
}
for (int i = 0; i < n; ++i) cout << when[i] << ' '; cout << endl;
const int logN = 19;
const int N = 1 << logN;
int sgt[2 * N];
fill(sgt, sgt + 2 * N, INF32);
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 (l += N, r += N; 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;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:169:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < n; ++i) cout << when[i] << ' '; cout << endl;
^~~
street_lamps.cpp:169:61: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < n; ++i) cout << when[i] << ' '; cout << endl;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
288 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
6 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
3704 KB |
Output is correct |
| 2 |
Correct |
89 ms |
3704 KB |
Output is correct |
| 3 |
Correct |
90 ms |
3704 KB |
Output is correct |
| 4 |
Correct |
109 ms |
7692 KB |
Output is correct |
| 5 |
Correct |
118 ms |
7948 KB |
Output is correct |
| 6 |
Correct |
95 ms |
7692 KB |
Output is correct |
| 7 |
Correct |
122 ms |
7560 KB |
Output is correct |
| 8 |
Correct |
127 ms |
8972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
288 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
6 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
100 ms |
3704 KB |
Output is correct |
| 9 |
Correct |
89 ms |
3704 KB |
Output is correct |
| 10 |
Correct |
90 ms |
3704 KB |
Output is correct |
| 11 |
Correct |
109 ms |
7692 KB |
Output is correct |
| 12 |
Correct |
118 ms |
7948 KB |
Output is correct |
| 13 |
Correct |
95 ms |
7692 KB |
Output is correct |
| 14 |
Correct |
122 ms |
7560 KB |
Output is correct |
| 15 |
Correct |
127 ms |
8972 KB |
Output is correct |
| 16 |
Incorrect |
9 ms |
4480 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
