Submission #712674

#	Time	Username	Problem	Language	Result	Execution time	Memory
712674		MISM06	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2698 ms	270400 KiB

street_lamps

//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kid 		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;
typedef pair < pii , pii > piiii;


const ll N = 3e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll rinf = -2e16;
const ll INF = 1e9 + 10;
const ll rINF = -1e9 - 10;
const ll lg = 32;

// phase one :
int n, q, a[N], ans[N]; //number of lamps, number of queries, situation of lamps, answer of query i;
set < piii > st; //blocks of equal lamps in type : {l, {r, situation}};
vector < piii > qu[N]; //queries in type of : {0, {idx, 0}} = {toggle of a[idx]} , {1, {l, r}} = {ask about segment [l, r]};
vector < piiii > timeline[N]; // orders of type : {{0, val} , {l, r}} = {{its ask, value that should plus anwer}, {segment of asking}}
								//, {{1, val}, {l, r}} = plus val to segments of segment [l, r];
vector < int > sgs[N]; //segments of asking in type : sgs[l] {r1, r2, ...};

piii find_block (int idx) {
	if (idx < 1 || idx > n) return {-1, {-1, -1}};
	auto it = st.lower_bound({idx + 1, {0, 0}});
	it = prev(it);
	return *it;
} //find block of idx;

// phase two : 

struct node {
	vector < int > Bit;
	vector < pii > Rs;
	int L, R, sz;
	void make (int l, int r) {
		L = l; R = r; 
		Bit.pb(rINF);
		Rs.pb({-1, -1});
		for (int i = l; i <= r; i++) 
			for (auto x : sgs[i]) 
				Rs.pb({x, i});
		sort(all(Rs));
		sz = Rs.sze; --sz;
		for (int i = 1; i <= sz; i++) Bit.pb(0);
	}
	int get_range (int idx) {
		auto it = lower_bound(all(Rs), make_pair(idx + 1, 0));
		if (it == Rs.end()) return sz;
		int res = it - Rs.begin();
		--res; return res;
	}
	int get_id (int l, int r) {
		return lower_bound(all(Rs), make_pair(r, l)) - Rs.begin();
	}
	void point (int val, int idx) {
		for (; idx <= sz; idx += (idx & -idx)) Bit[idx] += val;
	}
	void range (int val, int l, int r) {
		point(val, l);
		if (r < sz) point(-val, r + 1);
	}
	int read (int idx) {
		int res = 0;
		for (; idx > 0; idx -= (idx & -idx))
			res += Bit[idx];
		return res;
	}
} seg[N << 2];

void build (int v = 1, int tl = 1, int tr = n) {
	seg[v].make(tl, tr);
	if (tl == tr) return;
	kid;
	build (cl, tl, mid);
	build (cr, mid + 1, tr);
}

void upd (int Lpos, int Rpos, int val, int v = 1, int tl = 1, int tr = n) {
	if (tl >= Lpos) {
		int idx = seg[v].get_range(Rpos);
		if (idx) seg[v].range(val, 1, idx);
		return;
	}
	kid;
	if (Lpos <= mid) upd (Lpos, Rpos, val, cl, tl, mid);
	upd (Lpos, Rpos, val, cr, mid + 1, tr);
}

int ask (int Lpos, int Rpos, int v = 1, int tl = 1, int tr = n) {
	int res = 0;
	if (tl <= Lpos && Lpos <= tr) {
		int idx = seg[v].get_id(Lpos, Rpos);
		res += seg[v].read(idx);
	} 
	if (tl == tr) return res;
	kid;
	if (Lpos <= mid) return res + ask(Lpos, Rpos, cl, tl, mid);
	else return res + ask(Lpos, Rpos, cr, mid + 1, tr);
}

void solve () {

	//phase one :
	cin >> n >> q;
	st.insert({1, {n, 0}});
	for (int i = 1; i <= n; i++) {
		char ch; cin >> ch;
		if (ch == '1') qu[0].pb({0, {i, 0}});
	} //input of lamps;
	for (int i = 1; i <= q; i++) {
		string ty; cin >> ty;
		if (ty == "query") {
			int l, r; cin >> l >> r;
			qu[i].pb({1, {l, r - 1}});
		} else {
			int idx; cin >> idx;
			qu[i].pb({0, {idx, 0}});
		}
	} //input queries;
	for (int i = 0; i <= q; i++) {
		for (auto query : qu[i]) {
			if (query.F == 1) {
				int l = query.S.F, r = query.S.S;
				auto bl = find_block(l), br = find_block(r);
				int val = 0;
				if (bl == br && bl.S.S == 1) val = -1 * (q - i);
				timeline[i].pb({{0, val}, {l, r}});
				sgs[l].pb(r);
			} else {
				int idx = query.S.F;
				auto bi =  find_block(idx);
				if (a[idx] == 1) {
					int L = bi.F, R = bi.S.F;
					timeline[i].pb({{1, -1 * (q - i)}, {L, R}});
					if (L < idx) timeline[i].pb({{1, q - i}, {L, idx - 1}});
					if (R > idx) timeline[i].pb({{1, q - i}, {idx + 1, R}});

					st.erase(bi);
					int l = idx, r = idx;
					if (L < idx) st.insert({L, {idx - 1, 1}});
					else if (L > 1) {
						auto bl = find_block(idx - 1);
						st.erase(bl);
						l = bl.F;
					}
					if (R > idx) st.insert({idx + 1, {R, 1}});
					else if (R < n) {
						auto br = find_block(idx + 1);
						st.erase(br);
						r = br.S.F;
					}
					st.insert({l, {r, 0}});
					a[idx] = 0;
				} else {
					int L = bi.F, R = bi.S.F;
					st.erase(bi);
					int l = idx, r = idx;
					if (L < idx) st.insert({L, {idx - 1, 0}});
					else if (L > 1) {
						auto bl = find_block(idx - 1);
						st.erase(bl);
						timeline[i].pb({{1, -1 * (q - i)}, {bl.F, bl.S.F}});
						l = bl.F;
					}
					if (R > idx) st.insert({idx + 1, {R, 0}});
					else if (R < n) {
						auto br = find_block(idx + 1);
						st.erase(br);
						timeline[i].pb({{1, -1 * (q - i)}, {br.F, br.S.F}});
						r = br.S.F;
					}	
					timeline[i].pb({{1, q - i}, {l, r}});
					st.insert({l, {r, 1}});
					a[idx] = 1;
				}
			}
		}
	} //make timeline;

	// phase two :
	build();
	for (int i = 0; i <= q; i++) {
		ans[i] = rINF;
		for (auto o : timeline[i]) {
			if (o.F.F == 0) {
				ans[i] = ask(o.S.F, o.S.S);
				ans[i] += o.F.S;
			} else upd(o.S.F, o.S.S, o.F.S);
		}
	}
	for (int i = 1; i <= q; i++) if (ans[i] != rINF) cout << ans[i] << '\n';
}


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	

	int t = 1;
	// cin >> t;
	while (t--) {solve();}
    return 0;
}
/*
5 1
11011
query 1 2
*/
//inhonorofsbi;

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