제출 #409988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409988		yoavL	가로등 (APIO19_street_lamps)	C++14	20 / 100	5093 ms	17396 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 = 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+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;
	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


*/

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