#include <bits/stdc++.h>
using namespace std;
int n, q;
char a[300005], a_ret[300005];
vector<int> ps[300005], aib[300005];
vector<pair<int,int>> vv;
struct event
{
int tip, x, y;///doar x daca e tip 1 (upd), altfel tip 2 (query)
};
event v[300005];
void build_aib2d_stuff()
{
sort(vv.begin(), vv.end(), [](pair<int,int> A, pair<int,int> B)
{
return A.second < B.second;
});
for (int i = 1; i <= n; i++)
ps[i].push_back(0);
for (auto it : vv)
{
for (int i = it.first; i <= n; i += (i & -i))
if (ps[i].back() != it.second)
ps[i].push_back(it.second);
}
for (int i = 1; i <= n; i++)
aib[i].resize(ps[i].size());
}
int get_pos(int unde, int y)
{
int st = 0, pas = 1 << 19;
while (pas != 0)
{
if (st + pas < ps[unde].size() and ps[unde][st + pas] <= y)
st += pas;
pas /= 2;
}
if (ps[unde][st] != y)
while(true);
return st;
}
void update(int x, int y, int val)
{
for (int i = x; i <= n; i += (i & -i))
{
for (int j = get_pos(i,y); j < ps[i].size(); j += (j & -j))
aib[i][j] += val;
}
}
int query(int x, int y)
{
int rr = 0;
for (int i = x; i > 0; i -= (i & -i))
{
for (int j = get_pos(i, y); j > 0; j -= (j & -j))
rr += aib[i][j];
}
return rr;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i], a_ret[i] = a[i];
for (int i = 1; i <= q; i++)
{
string type;
cin >> type;
if (type == "toggle")
{
v[i].tip = 1;
cin >> v[i].x;
}
else
{
v[i].tip = 2;
cin >> v[i].x >> v[i].y, v[i].y--;
}
}
for (int i = 1; i <= q; i++)
{
if (v[i].tip == 2)
{
vv.push_back({v[i].x, n});
vv.push_back({v[i].x, v[i].y - 1});
}
}
set<pair<int,int>> scvmax;
map<pair<int,int>, int> beg;
int s = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] == '0')
{
if (s != 0)
{
scvmax.insert({s, i - 1});
s = 0;
}
s = 0;
}
else
{
if (s == 0)
s = i;
}
}
if (s != 0)
scvmax.insert({s, n});
for (int i = 1; i <= q; i++)
{
if (v[i].tip == 1)
{
int x = v[i].x;
if (a[x] == '0')
{
a[x] = '1';
bool lft = false, rgt = false;
if (x != 1 and a[x - 1] == '1')
lft = true;
if (x != n and a[x + 1] == '1')
rgt = true;
if (!lft and !rgt)
{
scvmax.insert({x,x});
beg[ {x,x}] = i;
}
else if (!lft and rgt)
{
pair<int,int> lol = *scvmax.lower_bound({x + 1, 0});
vv.push_back(lol);
scvmax.erase(lol);
scvmax.insert({x, lol.second});
beg[ {x,lol.second}] = i;
}
else if (lft and !rgt)
{
pair<int,int> lol = *prev(scvmax.lower_bound({x,0}));
vv.push_back(lol);
scvmax.erase(lol);
scvmax.insert({lol.first, x});
beg[ {lol.first,x}] = i;
}
else
{
pair<int,int> lolr = *scvmax.lower_bound({x + 1,0}), loll = *prev(scvmax.lower_bound({x,0}));
vv.push_back(loll);
vv.push_back(lolr);
scvmax.erase(loll);
scvmax.erase(lolr);
scvmax.insert({loll.first, lolr.second});
beg[ {loll.first, lolr.second}] = i;
}
}
else
{
a[x] = '0';
pair<int,int> pr = *prev(scvmax.lower_bound({x, n + 1}));
scvmax.erase(pr);
vv.push_back(pr);
if (pr.first != x)
{
scvmax.insert({pr.first, x - 1});
beg[ {pr.first, x - 1}] = i;
}
if (pr.second != x)
{
scvmax.insert({x + 1, pr.second});
beg[ {x + 1, pr.second}] = i;
}
}
}
}
build_aib2d_stuff();
scvmax.clear();
beg.clear();
s = 0;
for (int i = 1; i <= n; i++)
a[i] = a_ret[i];
for (int i = 1; i <= n; i++)
{
if (a[i] == '0')
{
if (s != 0)
{
scvmax.insert({s, i - 1});
s = 0;
}
s = 0;
}
else
{
if (s == 0)
s = i;
}
}
if (s != 0)
scvmax.insert({s, n});
for (int i = 1; i <= q; i++)
{
if (v[i].tip == 1)
{
int x = v[i].x;
if (a[x] == '0')
{
a[x] = '1';
bool lft = false, rgt = false;
if (x != 1 and a[x - 1] == '1')
lft = true;
if (x != n and a[x + 1] == '1')
rgt = true;
if (!lft and !rgt)
{
scvmax.insert({x,x});
beg[ {x,x}] = i;
}
else if (!lft and rgt)
{
pair<int,int> lol = *scvmax.lower_bound({x + 1, 0});
update(lol.first, lol.second, i - beg[lol]);
scvmax.erase(lol);
scvmax.insert({x, lol.second});
beg[ {x,lol.second}] = i;
}
else if (lft and !rgt)
{
pair<int,int> lol = *prev(scvmax.lower_bound({x,0}));
update(lol.first, lol.second, i - beg[lol]);
scvmax.erase(lol);
scvmax.insert({lol.first, x});
beg[ {lol.first,x}] = i;
}
else
{
pair<int,int> lolr = *scvmax.lower_bound({x + 1,0}), loll = *prev(scvmax.lower_bound({x,0}));
//cout << loll.first << ' ' << loll.second << ' ' << lolr.first << ' ' << lolr.second << endl;
update(loll.first, loll.second, i - beg[loll]);
update(lolr.first, lolr.second, i - beg[lolr]);
scvmax.erase(loll);
scvmax.erase(lolr);
scvmax.insert({loll.first, lolr.second});
beg[ {loll.first, lolr.second}] = i;
}
}
else
{
a[x] = '0';
pair<int,int> pr = *prev(scvmax.lower_bound({x, n + 1}));
scvmax.erase(pr);
update(pr.first, pr.second, i - beg[pr]);
if (pr.first != x)
{
scvmax.insert({pr.first, x - 1});
beg[ {pr.first, x - 1}] = i;
}
if (pr.second != x)
{
scvmax.insert({x + 1, pr.second});
beg[ {x + 1, pr.second}] = i;
}
}
}
else
{
int x = v[i].x, y = v[i].y;
int vl = query(x, n) - query(x, y - 1);
if (a[x] == '1')
{
pair<int,int> pr = *prev(scvmax.lower_bound({x, n + 1}));
//cout << i << ' ' << pr.first << ' ' << pr.second << endl;
if (pr.first <= x and pr.second >= y)
vl += i - beg[pr];
}
cout << vl << '\n';
}
}
return 0;
}
/**
Ma uit la secventele maximale de 1, eu vreau sa vad in cate momente a fost [x y] inclus intr-o secventa maximala
Daca retin, pentru fiecare secventa maximala, cat dureaza (termin cu ea cand se modifica), vreau suma(timp) pentru secventele care ma includ
Sa zicem ca atunci cand modific o secventa maximala o pun in "DS", o sa adun la raspuns, daca acum sunt intr-o secventa maximala, de cand e ea
Si fac O(N + Q) update-uri de forma: pentru fiecare (x, y) cu L <= x <= y <= R, adauga k si Q query-uri de forma: zi cat e un punct
Adica tehnic bag update cu +k in (L,R), si vreau suma pe dreptunghiul ((1,y), (x, N)) adica ((1,1), (x,N)) - ((1,1), (x, y - 1))
Yayy, aib 2d pe care nu l-am mai implementat vreodata
**/
Compilation message
street_lamps.cpp: In function 'int get_pos(int, int)':
street_lamps.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | if (st + pas < ps[unde].size() and ps[unde][st + pas] <= y)
| ~~~~~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void update(int, int, int)':
street_lamps.cpp:54:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int j = get_pos(i,y); j < ps[i].size(); j += (j & -j))
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
15708 KB |
Output is correct |
| 2 |
Execution timed out |
5094 ms |
15708 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5018 ms |
22288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5063 ms |
15964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5068 ms |
15964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
15708 KB |
Output is correct |
| 2 |
Execution timed out |
5094 ms |
15708 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
