Submission #649527

#	Time	Username	Problem	Language	Result	Execution time	Memory
649527		ymm	Street Lamps (APIO19_street_lamps)	C++17	60 / 100	1165 ms	524288 KiB

street_lamps

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

template<class T>
struct node
{
	T val;
	node *l, *r;
};

node<pii> pool[20000000];

template<class T>
node<T> *new_node()
{
	return new node<T>({});
}
template<>
node<pii> *new_node()
{
	static int nxt = 0;
	return &(pool[nxt++] = {});
}

template<class T, class F>
void up(int l, int r, F f, node<T> *t, int b, int e)
{
	//cerr << "up " << l << ' ' << r << " -> " << b << ' ' << e << '\n';
	if (l <= b && e <= r) {
		f(&t->val);
		return;
	}
	int mid = (b+e)/2;
	if (l < mid) {
		if (t->l == NULL)
			t->l = new_node<T>();
		up(l, r, f, t->l, b, mid);
	}
	if (mid < r) {
		if (t->r == NULL)
			t->r = new_node<T>();
		up(l, r, f, t->r, mid, e);
	}
}

template<class T, class F>
int get(int p, F f, node<T> *t, int b, int e)
{
	//cerr << "get " << p << " -> " << b << ' ' << e << '\n';
	int ans = f(&t->val);
	if (p <  (b+e)/2 && t->l)
		ans += get(p, f, t->l, b, (b+e)/2);
	if (p >= (b+e)/2 && t->r)
		ans += get(p, f, t->r, (b+e)/2, e);
	return ans;
}

const int N = 300'010;
string s;
int n, q;

set<pii> inter;
node<node<pii>> rt;

template<class F>
void up2d(int l, int r, F f)
{
	if (l >= r)
		return;
	up(l, r, [=](node<pii> *t) {
		up(l, r, f, t, 0, n);
	}, &rt, 0, n);
}

void init()
{
	s.push_back('0');
	int lst = -1;
	Loop (i,0,n+1) {
		if (lst == -1 && s[i] == '1') {
			lst = i;
		} else if (lst != -1 && s[i] != '1') {
			inter.insert({lst, i});
			lst = -1;
		}
	}
	for (auto [l, r] : inter) {
		//cerr << l << ' ' << r << " added\n";
		up2d(l, r, [](pii *x){*x = {1, 0};});
	}
}

void toggle(int i, int t)
{
	if (s[i] == '1') {
		auto it = --inter.upper_bound({i, N});
		auto [l, r] = *it;
		inter.erase(it);
		up2d(l  , r, [=](pii *x){*x = {x->first-1, x->second+t};});
		up2d(l  , i, [=](pii *x){*x = {x->first+1, x->second-t};});
		up2d(i+1, r, [=](pii *x){*x = {x->first+1, x->second-t};});
		s[i] = '0';
		if (l < i)
			inter.insert({l, i});
		if (i+1 < r)
			inter.insert({i+1, r});
	} else {
		auto it2 = inter.upper_bound({i, N});
		auto it1 = it2; --it1;
		int l = i, r = i+1;
		if (it2 != inter.end() && it2->first == i+1)
			r = it2->second;
		if (it2 != inter.begin() && it1->second == i)
			l = it1->first;
		if (r != i+1)
			inter.erase(it2);
		if (l != i)
			inter.erase(it1);
		up2d(l  , i, [=](pii *x){*x = {x->first-1, x->second+t};});
		up2d(i+1, r, [=](pii *x){*x = {x->first-1, x->second+t};});
		up2d(l  , r, [=](pii *x){*x = {x->first+1, x->second-t};});
		s[i] = '1';
		inter.insert({l, r});
	}
}

int get2d(int l, int r, int t)
{
	return get(l, [=](node<pii> *nd) {
		return get(r-1, [=](pii *x) {
			return x->first * t + x->second;
		}, nd, 0, n);
	}, &rt, 0, n);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> q;
	cin >> s; 
	init();
	Loop (t,1,q+1) {
		string s;
		cin >> s;
		if (s == "toggle") {
			int i;
			cin >> i;
			toggle(i-1, t);
		}
		if (s == "query") {
			int a, b;
			cin >> a >> b;
			--a; --b;
			if (a > b)
				swap(a, b);
			cout << get2d(a, b, t) << '\n';
		}
	}
}

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