/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 300000;
const int Q_MAX = 300000;
const int BUFFER_SIZE = 80000;
char buffer[BUFFER_SIZE];
int bpos = BUFFER_SIZE - 1;
char read_char ()
{
bpos++;
if(bpos == BUFFER_SIZE)
{
fread(buffer, sizeof(char), BUFFER_SIZE, stdin);
bpos = 0;
}
return buffer[bpos];
}
bool isDigit[] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int read_int ()
{
char c;
while(!isDigit[c = read_char()]);
int ans = 0;
do
{
ans = ans * 10 + c - '0';
}
while(isDigit[c = read_char()]);
return ans;
}
int n, q;
bool light[N_MAX + 2];
struct SGTNode
{
int len;
int pref;
int suff;
};
SGTNode join (const SGTNode &u, const SGTNode &v)
{
return SGTNode
{
u.len + v.len,
(u.pref == u.len ? u.len + v.pref : u.pref),
(v.suff == v.len ? v.len + u.suff : v.suff)
};
}
SGTNode SGT[N_MAX * 4 + 2];
void build (int node, int l, int r)
{
if(l == r)
{
SGT[node] = SGTNode{1, light[l], light[l]};
return;
}
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
build(lSon, l, mid);
build(rSon, mid + 1, r);
SGT[node] = join(SGT[lSon], SGT[rSon]);
}
void build ()
{
build(1, 1, n);
}
void update (int node, int l, int r, int upos)
{
if(l == r)
{
SGT[node].pref = 1 - SGT[node].pref;
SGT[node].suff = 1 - SGT[node].suff;
return;
}
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
if(upos <= mid)
update(lSon, l, mid, upos);
else
update(rSon, mid + 1, r, upos);
SGT[node] = join(SGT[lSon], SGT[rSon]);
}
void update (int upos)
{
update(1, 1, n, upos);
}
SGTNode query (int node, int l, int r, int ql, int qr)
{
if(ql <= l && r <= qr)
return SGT[node];
int mid = (l + r) / 2;
int lSon = node * 2, rSon = node * 2 + 1;
if(ql <= mid && mid + 1 <= qr)
return join(query(lSon, l, mid, ql, qr), query(rSon, mid + 1, r, ql, qr));
else if(ql <= mid)
return query(lSon, l, mid, ql, qr);
else
return query(rSon, mid + 1, r, ql, qr);
}
SGTNode query (int ql, int qr)
{
if(ql > qr)
return SGTNode{0, 0, 0};
return query(1, 1, n, ql, qr);
}
const int MOD = 223;
vector <pair <int, int>> BIT[(N_MAX + 1) + 2][MOD];
int* BITget (const int &i, const int &j)
{
int x = j % MOD;
for(pair <int, int> &p : BIT[i][x])
if(p.first == j)
return &p.second;
BIT[i][x].push_back(make_pair(j, 0));
return &BIT[i][x].back().second;
}
void BITupdate (int x, int y, int uval)
{
for(int i = x; i <= n + 1; i += i & -i)
for(int j = y; j >= 1; j -= j & -j)
*BITget(i, j) += uval;
}
int BITquery (int x, int y)
{
int answer = 0;
for(int i = x; i >= 1; i -= i & -i)
for(int j = y; j <= n + 1; j += j & -j)
answer += *BITget(i, j);
return answer;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
n = read_int();
q = read_int();
{
for(int i = 1; i <= n; i++)
light[i] = (read_char() == '1');
}
read_char();
build();
for(int i = 1; i <= n; i++)
if(light[i] == true)
{
int j = i;
while(j < n && light[j + 1] == true)
j++;
BITupdate(i, j + 1, + q);
i = j;
}
for(int qi = 1; qi <= q; qi++)
{
if(read_char() == 't')
{
int upos = read_int();
int lLen = query(1, upos - 1).suff;
int rLen = query(upos + 1, n).pref;
int l = upos - lLen;
int r = upos + 1 + rLen;
if(light[upos] == true)
{
BITupdate(l, r, - (q - qi));
BITupdate(l, upos, + (q - qi));
BITupdate(upos + 1, r, + (q - qi));
}
light[upos] = !light[upos];
update(upos);
if(light[upos] == true)
{
BITupdate(l, r, + (q - qi));
BITupdate(l, upos, - (q - qi));
BITupdate(upos + 1, r, - (q - qi));
}
}
else
{
int l = read_int();
int r = read_int();
int answer = BITquery(l, r);
if(query(l, r - 1).pref == r - l)
answer -= (q - qi);
cout << answer << "\n";
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'int read_int()':
street_lamps.cpp:55:22: warning: array subscript has type 'char' [-Wchar-subscripts]
55 | while(!isDigit[c = read_char()]);
| ~~^~~~~~~~~~~~~
street_lamps.cpp:61:21: warning: array subscript has type 'char' [-Wchar-subscripts]
61 | while(isDigit[c = read_char()]);
| ~~^~~~~~~~~~~~~
street_lamps.cpp: In function 'char read_char()':
street_lamps.cpp:28:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | fread(buffer, sizeof(char), BUFFER_SIZE, stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
249 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
242 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
235 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
249 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
249 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
