Submission #410486

#	Time	Username	Problem	Language	Result	Execution time	Memory
410486		yoavL	Street Lamps (APIO19_street_lamps)	C++14	40 / 100	5098 ms	253008 KiB

street_lamps

#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; }
void fix(pnode p) {
	if (p) {
		p->sum = p->p + sum(p->l) + sum(p->r);
	}
}
//split
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
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);
}
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);
}
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) {
			//merge(a[i], a[2 * i], a[2 * 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) {
				//wpr(l);
				ans += query(a[l], y);
				l++;
			}
			if (r % 2 == 0) {
				//wpr(r);
				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;
}



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);

}




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;
			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;
				// TODO: insert it in the segment
				//done.push_back(*left);
				//done[done.size() - (ll)1].second = time - done[done.size() - (ll)1].second;
				insert_per(left, time);
				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+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;
	// 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;
	
	insert_per(cur, time);
	segs.erase(cur);
}


void pr_segs()
{
	for (auto &it : segs) {
		pr_seg(it);
	}
}
void solve()
{
	cin >> n >> q;
	/*
	roots.push_back(new tr(0, n));
	rep(i, 1, n) {
		roots.push_back(new tr(roots[roots.size() - 1]));
	}
	*/
	seg.make(n);
	//wpr(roots.size());
	
	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;
					}
				}
				
			}
			//wpr(a);
			//wpr(roots.size());
			//res += roots[a]->q(0, b+1);
			//res += seg.q(a, b);
			ll add = seg.q(a, b);
			//wpr(add);
			res += add;
			//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


*/

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20