답안 #410485

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410485 2021-05-22T18:59:32 Z yoavL 가로등 (APIO19_street_lamps) C++14
40 / 100
5000 ms 258344 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 = 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.

*/

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


*/
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1866 ms 60452 KB Output is correct
2 Correct 2502 ms 75140 KB Output is correct
3 Correct 3493 ms 104216 KB Output is correct
4 Correct 4075 ms 160360 KB Output is correct
5 Correct 4569 ms 196404 KB Output is correct
6 Correct 4377 ms 188136 KB Output is correct
7 Correct 653 ms 15096 KB Output is correct
8 Correct 666 ms 16476 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 844 KB Output is correct
2 Correct 5 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 5068 ms 258344 KB Time limit exceeded
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 1016 ms 22612 KB Output is correct
6 Correct 2666 ms 103952 KB Output is correct
7 Correct 4332 ms 187572 KB Output is correct
8 Execution timed out 5097 ms 241920 KB Time limit exceeded
9 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 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 1866 ms 60452 KB Output is correct
9 Correct 2502 ms 75140 KB Output is correct
10 Correct 3493 ms 104216 KB Output is correct
11 Correct 4075 ms 160360 KB Output is correct
12 Correct 4569 ms 196404 KB Output is correct
13 Correct 4377 ms 188136 KB Output is correct
14 Correct 653 ms 15096 KB Output is correct
15 Correct 666 ms 16476 KB Output is correct
16 Correct 4 ms 844 KB Output is correct
17 Correct 5 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 5068 ms 258344 KB Time limit exceeded
21 Halted 0 ms 0 KB -