Submission #979178

#	Time	Username	Problem	Language	Result	Execution time	Memory
979178		c2zi6	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	5074 ms	328504 KiB

street_lamps

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
struct FENWICKTREE {
	VI a;
	VPI order;
	void init(int n) {
		a = VI(n);
		order.clear();
	}
	void add(int i, int s) {
		order.pb({i, s});
		while (i < a.size()) a[i] += s, i += i&-i;
	}
	int get(int i) {
		int ret = 0;
		while (i > 0) ret += a[i], i -= i&-i;
		return ret;
	}
	void clear() {
		while (order.size()) {
			auto[i, s] = order.back();
			order.pop_back();
			add(i, -s);
			order.pop_back();
		}
	}
} BIT;
struct POINT {
	int x, y, z, val, ind;
};
int n;
VI ret;
vector<POINT> v;
void CDQ(int l, int r) {
	if (l == r) return;
	int m = (l + r) / 2;
	CDQ(l, m), CDQ(m+1, r);
	vector<POINT> tmp;
	int i = l, j = m+1;
	while (i <= m && j <= r) {
		if (v[i].y <= v[j].y) BIT.add(v[i].z, v[i].val), tmp.pb(v[i++]);
		else ret[v[j].ind] += BIT.get(v[j].z-1), tmp.pb(v[j++]);
	}
	while (i <= m) BIT.add(v[i].z, v[i].val), tmp.pb(v[i++]);
	while (j <= r) ret[v[j].ind] += BIT.get(v[j].z-1), tmp.pb(v[j++]);
	replr(i, l, r) v[i] = tmp[i-l];
	BIT.clear();
}
void CDQ() {
	sort(all(v), [](POINT a, POINT b){
			return make_tuple(a.x, a.y, a.z) < make_tuple(b.x, b.y, b.z);
		});
	n = v.size();
	ret = VI(n+1);
	BIT.init(4e5);
	CDQ(0, n-1);
}
VI sol(vector<POINT> add, vector<POINT> get) {
	VI ans(get.size()+1);
	v.clear();
	rep(i, add.size()) v.pb(add[i]);
	rep(i, get.size()) v.pb(get[i]);
	CDQ();
 
	replr(i, 1, get.size()) ans[i] = ret[i] * get[i-1].z;
	rep(i, add.size()) add[i].val *= add[i].z;
 
	v.clear();
	rep(i, add.size()) v.pb(add[i]);
	rep(i, get.size()) v.pb(get[i]);
	CDQ();
	replr(i, 1, get.size()) ans[i] -= ret[i];
	return ans;
}
 
vector<POINT> avel;
vector<POINT> harc;
void add(int i, int j, int s, int t) {
	/* cout << i << " " << j << " " << s << endl; */
	avel.pb({i, i, t, s, 0});
	avel.pb({i, j+1, t, -s, 0});
	avel.pb({j+1, i, t, -s, 0});
	avel.pb({j+1, j+1, t, s, 0});
}

struct SEGTREEF {
	int n;
	vector<int> tree;
	int upd(int N, int L, int R, int i, int s) {
		if (i < L || i > R) return tree[N];
		if (L == R) {
			if (s == 0) tree[N] = i;
			else tree[N] = 1e9;
			return tree[N];
		}
		int M = (L + R) / 2;
		return tree[N] = min(upd(N*2+1, L, M, i, s), upd(N*2+2, M+1, R, i, s));
	}
	int get(int N, int L, int R, int l, int r) {
		if (l <= L && R <= r) return tree[N];
		if (R < l || L > r) return 2e9;
		int M = (L + R) / 2;
		return min(get(N*2+1, L, M, l, r), get(N*2+2, M+1, R, l, r));
	}
	SEGTREEF(int sz) {
		n = 1;
		while (n < sz) n *= 2;
		tree = vector<int>(2*n, 2e9);
	}
	
	void upd(int i, int s) {
		upd(0, 0, n-1, i, s);
	}
	int get(int l, int r) {
		return get(0, 0, n-1, l, r);
	}
};
struct SEGTREEL {
	int n;
	vector<int> tree;
	int upd(int N, int L, int R, int i, int s) {
		if (i < L || i > R) return tree[N];
		if (L == R) {
			if (s == 0) tree[N] = i;
			else tree[N] = -1e9;
			return tree[N];
		}
		int M = (L + R) / 2;
		return tree[N] = max(upd(N*2+1, L, M, i, s), upd(N*2+2, M+1, R, i, s));
	}
	int get(int N, int L, int R, int l, int r) {
		if (l <= L && R <= r) return tree[N];
		if (R < l || L > r) return 2e9;
		int M = (L + R) / 2;
		return max(get(N*2+1, L, M, l, r), get(N*2+2, M+1, R, l, r));
	}
	SEGTREEL(int sz) {
		n = 1;
		while (n < sz) n *= 2;
		tree = vector<int>(2*n, 2e9);
	}
	
	void upd(int i, int s) {
		upd(0, 0, n-1, i, s);
	}
	int get(int l, int r) {
		return get(0, 0, n-1, l, r);
	}
};

 
void solve() {
	int n, q;
	cin >> n >> q;
	VI a(n);
	rep(i, n) {
		char ch;
		cin >> ch;
		a[i] = (ch == '1');
	}

	/* set<int> zeros; */
	/* rep(i, n) if (!a[i]) zeros.insert(i); */
	/* zeros.insert(-1); */
	/* zeros.insert(n); */
	SEGTREEF segf(n);
	SEGTREEL segl(n);
	rep(i, n) segf.upd(i, a[i]);
	rep(i, n) segl.upd(i, a[i]);

	auto fn = [&](int i){
		int ret = segf.get(i, 1e9);
		if (ret == 1e9) return n;
		for (int j = i; j < n; j++) if (a[j] == 0) return j;
		return n;
	};
	auto ln = [&](int i){
		int ret = segf.get(-1e9, i);
		if (ret == -1e9) return -1;
		for (int j = i; j >= 0; j--) if (a[j] == 0) return j;
		return -1;
	};
	for (int i = 0; i < n; i++) if (a[i]) {
		int j = fn(i)-1;
		add(i+1, j+1, +1, 1);
		i = j;
	}

	/* while (true) { */
	/* 	string t; */
	/* 	cin >> t; */
	/* 	if (t == "upd") { */
	/* 		int i; */
	/* 		cin >> i; */
	/* 		i--; */
	/* 		if (a[i] == 0) { */
	/* 			a[i] = 1; */
	/* 			segf.upd(i, 1); */
	/* 		} else { */
	/* 			a[i] = 0; */
	/* 			segf.upd(i, 0); */
	/* 		} */
	/* 		for (int x : a) cout << x; cout << endl; */
	/* 	} else { */
	/* 		int i; */
	/* 		cin >> i; */
	/* 		i--; */
	/* 		cout << segf.get(i, 1e9)+1 << endl; */
	/* 	} */
	/* } */
 
	rep(tm, q) {
		string t;
		cin >> t;
		if (t == "query") {
			int l, r;
			cin >> l >> r;
			harc.pb({l, r-1, tm+2, 0, (int)harc.size()+1});
		} else {
			int i;
			cin >> i;
			i--;
			if (a[i] == 0) {
				a[i] = 1;
				segf.upd(i, 1);
				segl.upd(i, 1);
				if (i < n-1 && a[i+1]) {
					add(i+2, fn(i+1), -1, tm+2);
				}
				if (i > 0 && a[i-1]) {
					add(ln(i-1)+2, i, -1, tm+2);
				}
				add(ln(i)+2, fn(i), +1, tm+2);
			} else if (a[i] == 1) {
				add(ln(i)+2, fn(i), -1, tm+2);
				a[i] = 0;
				segf.upd(i, 0);
				segl.upd(i, 0);
				if (i < n-1 && a[i+1]) {
					add(i+2, fn(i+1), +1, tm+2);
				}
				if (i > 0 && a[i-1]) {
					add(ln(i-1)+2, i, +1, tm+2);
				}
			}
		}
	}
	VI ans = sol(avel, harc);
	replr(i, 1, harc.size()) cout << ans[i] << " "; cout << endl;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    /* cin >> t; */
    while (t--) solve();
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void FENWICKTREE::add(int, int)':
street_lamps.cpp:42:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   while (i < a.size()) a[i] += s, i += i&-i;
      |          ~~^~~~~~~~~~
street_lamps.cpp: In member function 'void FENWICKTREE::clear()':
street_lamps.cpp:51:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |    auto[i, s] = order.back();
      |        ^
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:7:24: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    7 | #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
      |                        ^~~
street_lamps.cpp:279:2: note: in expansion of macro 'replr'
  279 |  replr(i, 1, harc.size()) cout << ans[i] << " "; cout << endl;
      |  ^~~~~
street_lamps.cpp:279:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  279 |  replr(i, 1, harc.size()) cout << ans[i] << " "; cout << endl;
      |                                                  ^~~~

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