#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 = long long;
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.
*/
ll n, q;
vb arr;
struct custom_compare final
{
bool operator() (const pair<pll, ll>& left, const pair<pll, ll>& right) const
{
return (left.first.first < right.first.first);
}
};
/*
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;
}
void unite_case(ll i, ll time)
{
arr[i] = 1;
//segs.insert({ { i, i }, time });
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;
// TODO: insert it in the segment
done.push_back(*right);
done[done.size() - (ll)1].second = time - done[done.size() - (ll)1].second;
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;
// TODO: insert it in the segment
done.push_back(*left);
done[done.size() - (ll)1].second = time - done[done.size() - (ll)1].second;
s = left->first.first;
}
}
}
//wpr(s);
//wpr(e);
segs.insert({ { s, e }, time });
if (erright) {
segs.erase(right);
}
if (erleft) {
segs.erase(left);
}
}
void divide_case(ll i, ll time)
{
arr[i] = 0;
auto cur = segs.lower_bound({ {i, 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;
// TODO: insert it in the segment
if(s <= i - 1) segs.insert({ {s, i - 1}, time });
if(i + 1 <= e) segs.insert({ {i+1, e}, time });
done.push_back(*cur);
done[done.size() - (ll)1].second = time - done[done.size() - (ll)1].second;
segs.erase(cur);
}
void pr_segs()
{
for (auto &it : segs) {
pr_seg(it);
}
}
void solve()
{
cin >> n >> q;
arr.resize(n);
rep(i, 0, n) {
char c;
cin >> c;
arr[i] = c - '0';
}
//wprv(arr);
{
ll i = 0;
while (i < n) {
if (arr[i] == 0) {
i++;
continue;
}
ll s = i;
while (i+1 < n && arr[i+1] == 1) {
i++;
}
//s.insert({ {s, i}, (ll)0 });
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()) {
//pr("printing it:");
//pr_seg(*it);
if (it->first.first <= a && it->first.second >= b) {
res += t - it->second;
}
}
}
//pr("printing done:");
for (auto& v : done) {
//pr_seg(v);
if (v.first.first <= a && v.first.second >= b) {
res += v.second;
}
}
//pr("---------------------------");
pr(res);
}
//pr_segs();
}
}
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
*/
| # |
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 |
Execution timed out |
5084 ms |
3456 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
3 ms |
320 KB |
Output is correct |
| 5 |
Correct |
1445 ms |
21720 KB |
Output is correct |
| 6 |
Execution timed out |
5051 ms |
10348 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
2805 ms |
11600 KB |
Output is correct |
| 6 |
Execution timed out |
5071 ms |
10316 KB |
Time limit exceeded |
| 7 |
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 |
- |
