#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <fstream>
#include <iomanip>
using namespace std;
using ll = int;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using pb = pair<bool, bool>;
using vpb = vector<pb>;
using vvpb = vector<vpb>;
using vi = vector<int>;
using vvi = vector<vi>;
const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e18;
#define FAST ios_base::sync_with_stdio(0)
#define FASTIN cin.tie(0)
#define FASTOUT cout.tie(0)
#define upmin(a, b) a = min(a, b)
#define upmax(a, b) a = max(a, b)
#define pr(x) cout << x << endl;
#define prv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define prvv(v) for(auto it : v) { for(auto it2 : it) cout << it2 << " "; cout << endl; } cout << endl;
#define wpr(x) cout << #x << " = " << (x) << endl;
#define wprv(v) cout << #v << ": " << endl; for(auto it : v) cout << it << " "; cout << endl;
#define wprvv(v) cout << #v << ": " << endl; for(auto it : v) { for(auto it2 : it) cout << it2 << " "; cout << endl; } cout << endl;
#define rep(i,s,e) for(ll i = s; i < e; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
/*
Solution:
Each moment we have segments of reachable nodes.
We will store them in a set.
We will also store their start time.
Each time we get a flip, we change (at most) 2 segments.
So we can take them out and make (at most) 2 other segments.
Each time we get a query of (a, b), we have to find the number of segments (x, y) that fufill:
x <= a <= b <= y
This can be done using persistent segment tree ig.
*/
struct node {
node* l = 0, * r = 0;
int b, p, sum;
int pri;
node(int b, int p) : b(b), p(p), sum(p), pri(rand()) {}
};
using pnode = node*;
int sum(pnode p) { return p ? p->sum : 0; }
inline void fix(pnode p) {
if (p) {
p->sum = p->p + sum(p->l) + sum(p->r);
}
}
//split
inline void split(pnode p, pnode & l, pnode & r, int b) {
if (!p) { l = r = 0; return; }
if (p->b < b) l = p, split(p->r, p->r, r, b);
else r = p, split(p->l, l, p->l, b);
fix(p);
}
//merge
inline void merge(pnode & p, pnode l, pnode r) {
if (!l || !r) p = l ? l : r;
else {
if (l->pri > r->pri) p = l, merge(l->r, l->r, r);
else p = r, merge(r->l, l, r->l);
}
fix(p);
}
inline void insert(pnode & t, int b, int p) {
pnode l, r;
split(t, l, r, b);
merge(r, new node(b, p), r);
merge(t, l, r);
}
inline int query(pnode t, int y) {
pnode l, r;
split(t, l, r, y);
int ans = sum(r);
merge(t, l, r);
return ans;
}
struct SEG {
vector<pnode> a;
ll sz;
void make(ll n) {
for (sz = 1; sz < n; sz <<= 1);
a.resize(2 * sz);
}
void up(ll i, ll b, ll p)
{
i += sz;
insert(a[i], b, p);
for (i >>= 1; i; i >>= 1) {
insert(a[i], b, p);
}
}
ll q(ll x, ll y) {
ll l = 0, r = x;
l += sz, r += sz;
ll ans = 0;
while (l <= r) {
if (l % 2 == 1) {
ans += query(a[l], y);
l++;
}
if (r % 2 == 0) {
ans += query(a[r], y);
r--;
}
l >>= 1, r >>= 1;
}
return ans;
}
};
SEG seg;
ll n, q;
vb arr;
/*
Our set. {{start, end}, insertion time}
*/
set< pair<pair<ll, ll>, ll> > segs;
vector<pair<pll, ll>> done;
void pr_seg(pair<pll, ll> p)
{
cout << "start: " << p.first.first << ", end: " << p.first.second << ", insertion time: " << p.second << endl;
}
inline void insert_per(set<pair<pll, ll>>::iterator &p, ll time)
{
ll s = p->first.first;
ll e = p->first.second;
ll v = time - p->second;
seg.up(s, e, v);
//roots[s]->up(e, v);
}
inline void unite_case(ll i, ll time)
{
arr[i] = 1;
ll s = i, e = i;
auto right = segs.lower_bound({ {s, e}, (ll)0 });
bool erright = false, erleft = false;
if (right != segs.end()) {
if (right->first.first == e + 1) {
erright = true;
insert_per(right, time);
e = right->first.second;
}
}
auto left = segs.end();
if (right != segs.begin())
{
left = prev(right);
if (left != segs.end()) {
if (left->first.second == s - 1) {
erleft = true;
insert_per(left, time);
s = left->first.first;
}
}
}
segs.insert({ { s, e }, time });
if (erright) {
segs.erase(right);
}
if (erleft) {
segs.erase(left);
}
}
inline void divide_case(ll i, ll time)
{
arr[i] = 0;
auto cur = segs.lower_bound({ {i+1, 0}, (ll)0 });
if (cur == segs.begin()) return;
cur = prev(cur);
ll s = cur->first.first;
ll e = cur->first.second;
if (e < i) return;
if(s <= i - 1) segs.insert({ {s, i - 1}, time });
if(i + 1 <= e) segs.insert({ {i+1, e}, time });
insert_per(cur, time);
segs.erase(cur);
}
void pr_segs()
{
for (auto &it : segs) {
pr_seg(it);
}
}
void solve()
{
cin >> n >> q;
seg.make(n);
arr.resize(n);
rep(i, 0, n) {
char c;
cin >> c;
arr[i] = c - '0';
}
{
ll i = 0;
while (i < n) {
if (arr[i] == 0) {
i++;
continue;
}
ll s = i;
while (i+1 < n && arr[i+1] == 1) {
i++;
}
segs.insert({ {s, i}, (ll)0 });
i++;
}
}
rep(t, 1, q + 1) {
string type;
cin >> type;
if (type == "toggle") {
ll i; cin >> i; i--;
if (arr[i] == 0) unite_case(i, t);
else divide_case(i, t);
}
else {
ll a, b;
cin >> a >> b;
a--, b -= 2;
ll res = 0;
auto it = segs.upper_bound({ {b+1, 0}, 0 });
if (it != segs.begin()) {
it = prev(it);
if (it != segs.end()) {
if (it->first.first <= a && it->first.second >= b) {
res += t - it->second;
}
}
}
ll add = seg.q(a, b);
pr(res);
}
}
}
int main()
{
FAST;
FASTIN; FASTOUT;
solve();
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
7 1000
1011011
7 1000
0000000
*/
Compilation message
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:305:7: warning: unused variable 'add' [-Wunused-variable]
305 | ll add = seg.q(a, b);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1827 ms |
56628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
844 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
