Submission #979129

#	Time	Username	Problem	Language	Result	Execution time	Memory
979129		c2zi6	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	5015 ms	320812 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});
}

void solve() {
	/* int n; */
	/* cin >> n; */
	/* for (int tm = 1; tm <= n; tm++) { */
	/* 	string t; */
	/* 	cin >> t; */
	/* 	if (t == "ADD") { */
	/* 		int cnt; */
	/* 		cin >> cnt; */
	/* 		while (cnt--) { */
	/* 			int l, r, s; */
	/* 			cin >> l >> r >> s; */
	/* 			add(l, r, s, tm); */
	/* 		} */
	/* 	} else { */
	/* 		int l, r; */
	/* 		cin >> l >> r; */
	/* 		r--; */
	/* 		harc.pb({l, r, tm, 0, (int)harc.size()+1}); */
	/* 	} */
	/* } */

	int n, q;
	cin >> n >> q;
	VI a(n);
	rep(i, n) {
		char ch;
		cin >> ch;
		a[i] = (ch == '1');
	}
	auto fn = [&](int i){
		for (int j = i; j < n; j++) if (a[j] == 0) return j;
		return n;
	};
	auto ln = [&](int i){
		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;
	}

	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;
				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;
				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:193:2: note: in expansion of macro 'replr'
  193 |  replr(i, 1, harc.size()) cout << ans[i] << " "; cout << endl;
      |  ^~~~~
street_lamps.cpp:193:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  193 |  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