oj.uz

답안 #410486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410486 2021-05-22T19:04:44 Z yoavL 가로등 (APIO19_street_lamps) C++14
40 / 100
 5000 ms 253008 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; }
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.0 / 20.0

# 결과 실행 시간 메모리 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 332 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1939 ms 57248 KB Output is correct
2 Correct 2555 ms 71648 KB Output is correct
3 Correct 3472 ms 100164 KB Output is correct
4 Correct 4009 ms 155024 KB Output is correct
5 Correct 4640 ms 190800 KB Output is correct
6 Correct 4507 ms 183248 KB Output is correct
7 Correct 671 ms 9160 KB Output is correct
8 Correct 661 ms 10460 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 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 204 KB Output is correct
5 Execution timed out 5098 ms 253008 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 4 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 1029 ms 16532 KB Output is correct
6 Correct 2734 ms 98464 KB Output is correct
7 Correct 4484 ms 182444 KB Output is correct
8 Execution timed out 5092 ms 230576 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1939 ms 57248 KB Output is correct
9 Correct 2555 ms 71648 KB Output is correct
10 Correct 3472 ms 100164 KB Output is correct
11 Correct 4009 ms 155024 KB Output is correct
12 Correct 4640 ms 190800 KB Output is correct
13 Correct 4507 ms 183248 KB Output is correct
14 Correct 671 ms 9160 KB Output is correct
15 Correct 661 ms 10460 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 204 KB Output is correct
20 Execution timed out 5098 ms 253008 KB Time limit exceeded
21 Halted 0 ms 0 KB -