oj.uz

Submission #410487

# Submission time Handle Problem Language Result Execution time Memory
410487 2021-05-22T19:06:57 Z yoavL Street Lamps (APIO19_street_lamps) C++14
40 / 100
 5000 ms 266876 KB 
#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) {
			//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;
}



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

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;
	// 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1751 ms 57148 KB Output is correct
2 Correct 2345 ms 71748 KB Output is correct
3 Correct 3365 ms 100408 KB Output is correct
4 Correct 3763 ms 155232 KB Output is correct
5 Correct 4391 ms 190860 KB Output is correct
6 Correct 4244 ms 183084 KB Output is correct
7 Correct 630 ms 9156 KB Output is correct
8 Correct 648 ms 10580 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 844 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 4 ms 588 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Execution timed out 5087 ms 266876 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 4 ms 588 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 960 ms 16612 KB Output is correct
6 Correct 2547 ms 98488 KB Output is correct
7 Correct 4077 ms 182416 KB Output is correct
8 Execution timed out 5091 ms 245796 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1751 ms 57148 KB Output is correct
9 Correct 2345 ms 71748 KB Output is correct
10 Correct 3365 ms 100408 KB Output is correct
11 Correct 3763 ms 155232 KB Output is correct
12 Correct 4391 ms 190860 KB Output is correct
13 Correct 4244 ms 183084 KB Output is correct
14 Correct 630 ms 9156 KB Output is correct
15 Correct 648 ms 10580 KB Output is correct
16 Correct 4 ms 844 KB Output is correct
17 Correct 4 ms 716 KB Output is correct
18 Correct 4 ms 588 KB Output is correct
19 Correct 3 ms 332 KB Output is correct
20 Execution timed out 5087 ms 266876 KB Time limit exceeded
21 Halted 0 ms 0 KB -