Submission #555699

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
555699	2022-05-01T11:05:14 Z	Zanite	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	3894 ms	286604 KB

street_lamps

// "I assure you that you guys won't make it to the top 4"
// - Tzaph, 21 December 2021

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ll long long
#define ld long double
#define si short int
#define i8 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define psi pair<si, si>
#define pi8 pair<i8, i8>
#define pq priority_queue
#define fi first
#define se second

#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'

#define yume using
#define wo namespace
#define kanaeyo std
#define nazotte __gnu_pbds

yume wo kanaeyo;
yume wo nazotte;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
 
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
 
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}

const ll ModA = 998244353;
const ll ModC = 1e9 + 7;
const ll INF = 1e18;
const ll iINF = 1e9;

const ld EPS = 1e-9;
const ld iEPS = 1e-6;

const int maxN = 3e5 + 5;

struct FenwickTree {
	ll sz;
	vector<ll> BIT;

	FenwickTree(ll _sz) {
		sz = _sz;
		BIT.assign(_sz+1, 0);
	}

	void update(ll idx, ll val) {
		for (; idx <= sz; idx += (idx & -idx)) {
			BIT[idx] += val;
		}
	}

	ll sum(ll idx) {
		ll ret = 0;
		idx = min(idx, sz);
		for (; idx > 0; idx -= (idx & -idx)) {
			ret += BIT[idx];
		}
		return ret;
 	}

	ll query(ll l, ll r) {
		return sum(r) - sum(l-1);
	}
};

struct FenwickTree2D {
	ll sz;
	vector<FenwickTree> inner;
	vector<vector<ll>> pos;

	FenwickTree2D(ll _sz) {
		sz = _sz;
		pos.assign(_sz + 1, vector<ll>(0));
	}

	void addPos(ll d1, ll d2) {
		for (; d1 <= sz; d1 += (d1 & -d1)) {
			pos[d1].push_back(d2);
		}
	}

	void build() {
		for (ll i = 0; i <= sz; i++) {
			sort(pos[i].begin(), pos[i].end());
			pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());

			inner.push_back(FenwickTree(pos[i].size()));
		}
	}

	void update(ll d1, ll d2, ll val) {
		for (; d1 <= sz; d1 += (d1 & -d1)) {
			ll d2_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2) - pos[d1].begin() + 1;
			//cout << d1 << ' ' << d2 << ' ' << d2_compressed << '\n';
			inner[d1].update(d2_compressed, val);
		}
	}

	ll sum(ll d1, ll d2l, ll d2r) {
		ll ret = 0;
		for (; d1 > 0; d1 -= (d1 & -d1)) {
			ll d2l_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2l) - pos[d1].begin() + 1;
			ll d2r_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2r) - pos[d1].begin() + 1;
			//cout << d1 << ' ' << d2l_compressed << ' ' << d2r_compressed << '\n';
			ret += inner[d1].query(d2l_compressed, d2r_compressed);
		}
		return ret;
	}

	ll query(ll d1l, ll d1r, ll d2l, ll d2r) {
		//cout << sum(d1r, d2l, d2r) << ' ' << sum(d1l-1, d2l, d2r) << '\n';
		return sum(d1r, d2l, d2r) - sum(d1l-1, d2l, d2r);
	}

	void printPos() {
		for (ll i = 1; i <= sz; i++) {
			cout << i << ": ";
			for (auto j : pos[i]) {cout << j << " ";}
			cout << '\n';
		}
	}

	void print() {
		for (ll i = 1; i <= sz; i++) {
			cout << i << ": ";
			for (auto j : pos[i]) {
				cout << "{" << j << ": " << query(i, i, j, j) << "} ";
			}
			cout << '\n';
		}
	}
};

struct Operation {
	bool typ; // 0 = update, 1 = query
	ll x1, y1, x2, y2, t;
	pll val;

	Operation(ll _x1, ll _y1, pll _val) {
		typ = 0;
		x1 = _x1, y1 = _y1, val = _val;
	}

	Operation(ll _x1, ll _y1, ll _x2, ll _y2, ll _t) {
		typ = 1;
		x1 = _x1, y1 = _y1, x2 = _x2, y2 = _y2, t = _t;
	}
};

int n, q;
bool lamps[maxN];
set<pll> segments;
vector<Operation> op;

int main() {
	scanf("%d %d", &n, &q);

	char c;
	for (int i = 1; i <= n; i++) {
		scanf(" %c", &c);
		lamps[i] = (c == '1');
	}

	FenwickTree2D values = FenwickTree2D(n);
	FenwickTree2D toggled = FenwickTree2D(n);

	// NOTE: because we need <= operator in lower_bound,
	// all set elements are negative

	for (int start = -1, i = 1; i <= n+1; i++) {
		if (lamps[i]) {
			if (start == -1) {start = i;}
		} else {
			if (start != -1) {
				segments.insert({-start, -(i-1)});

				values.addPos(start, i-1);
				toggled.addPos(start, i-1);
				op.push_back(Operation(start, i-1, {q, 1}));

				start = -1;
			}
		}
	}

	char typ[10];
	for (int a, b, i = 1; i <= q; i++) {
		scanf(" %s", typ);
		if (typ[0] == 't') {
			scanf("%d", &a);
			if (lamps[a]) {
				// toggle the lamp off

				// remove segment of current lamp
				auto cseg_it = segments.lower_bound({-a, -iINF});
				pll cseg = *cseg_it;
				//cout << "cseg " << cseg.fi << ' ' << cseg.se << '\n';
				segments.erase(cseg);

				values.addPos(-cseg.fi, -cseg.se);
				toggled.addPos(-cseg.fi, -cseg.se);
				op.push_back(Operation(-cseg.fi, -cseg.se, {-(q-i), -1}));

				// insert new segments (except if it's of length 0)

				// left segment
				if (a != -cseg.fi) {
					segments.insert({cseg.fi, -(a-1)});

					values.addPos(-cseg.fi, a-1);
					toggled.addPos(-cseg.fi, a-1);
					op.push_back(Operation(-cseg.fi, a-1, {q-i, 1}));
				}
				// right segment
				if (a != -cseg.se) {
					segments.insert({-(a+1), cseg.se});

					values.addPos(a+1, -cseg.se);
					toggled.addPos(a+1, -cseg.se);
					op.push_back(Operation(a+1, -cseg.se, {q-i, 1}));
				}

			} else {
				// toggle the lamp on
				pll newseg = {-a, -a};

				// check if lamps next to it are on

				// left
				if (lamps[a-1]) {
					auto lseg_it = segments.lower_bound({-(a-1), -iINF});
					pll lseg = *lseg_it;
					newseg.fi = lseg.fi;
					segments.erase(lseg);

					values.addPos(-lseg.fi, -lseg.se);
					toggled.addPos(-lseg.fi, -lseg.se);
					op.push_back(Operation(-lseg.fi, -lseg.se, {-(q-i), -1}));
				}
				// right
				if (lamps[a+1]) {
					auto rseg_it = segments.lower_bound({-(a+1), -iINF});
					pll rseg = *rseg_it;
					newseg.se = rseg.se;
					segments.erase(rseg);

					values.addPos(-rseg.fi, -rseg.se);
					toggled.addPos(-rseg.fi, -rseg.se);
					op.push_back(Operation(-rseg.fi, -rseg.se, {-(q-i), -1}));
				}

				// insert new segment
				segments.insert(newseg);
				values.addPos(-newseg.fi, -newseg.se);
				toggled.addPos(-newseg.fi, -newseg.se);
				op.push_back(Operation(-newseg.fi, -newseg.se, {q-i, 1}));
			}

			lamps[a] = !lamps[a];

		} else {
			scanf("%d %d", &a, &b);

			op.push_back(Operation(1, b-1, a, n, i));
		}

		//for (auto i : segments) {cout << "{" << i.fi << ", " << i.se << "} ";}
		//cout << '\n';
		//D.print();
		//cout << '\n';
	}

	values.build();
	toggled.build();

	//values.printPos();
	//toggled.printPos();

	for (auto O : op) {
		if (O.typ == 0) {
			//printf("Update %lld %lld with %lld %lld\n", O.x1, O.y1, O.val.fi, O.val.se);
			values.update(O.x1, O.y1, O.val.fi);
			toggled.update(O.x1, O.y1, O.val.se);

			//values.print();
			//toggled.print();
		} else {
			//printf("Query (%lld %lld) to (%lld %lld) at time %lld\n", O.x1, O.y1, O.x2, O.y2, O.t);
			ll v = values.query(O.x1, O.x2, O.y1, O.y2);
			ll t = toggled.query(O.x1, O.x2, O.y1, O.y2);
			//printf("%lld %lld\n", v, t);
			ll fin = v - (1ll * t * (q-O.t));
			printf("%lld\n", fin);
		}
	}
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:181:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:185:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |   scanf(" %c", &c);
      |   ~~~~~^~~~~~~~~~~
street_lamps.cpp:213:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |   scanf(" %s", typ);
      |   ~~~~~^~~~~~~~~~~~
street_lamps.cpp:215:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |    scanf("%d", &a);
      |    ~~~~~^~~~~~~~~~
street_lamps.cpp:287:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  287 |    scanf("%d %d", &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	329 ms	51256 KB	Output is correct
2	Correct	451 ms	57368 KB	Output is correct
3	Correct	814 ms	70884 KB	Output is correct
4	Correct	2543 ms	202492 KB	Output is correct
5	Correct	2446 ms	195404 KB	Output is correct
6	Correct	2873 ms	212564 KB	Output is correct
7	Correct	300 ms	87424 KB	Output is correct
8	Correct	298 ms	88828 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	852 KB	Output is correct
2	Correct	3 ms	852 KB	Output is correct
3	Correct	3 ms	708 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	3655 ms	239792 KB	Output is correct
6	Correct	3191 ms	223260 KB	Output is correct
7	Correct	2355 ms	197476 KB	Output is correct
8	Correct	303 ms	88888 KB	Output is correct
9	Correct	117 ms	19216 KB	Output is correct
10	Correct	133 ms	36316 KB	Output is correct
11	Correct	129 ms	36348 KB	Output is correct
12	Correct	281 ms	87480 KB	Output is correct
13	Correct	289 ms	88936 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	3 ms	840 KB	Output is correct
4	Correct	4 ms	976 KB	Output is correct
5	Correct	974 ms	123060 KB	Output is correct
6	Correct	1862 ms	163608 KB	Output is correct
7	Correct	2759 ms	211812 KB	Output is correct
8	Correct	3894 ms	286604 KB	Output is correct
9	Correct	511 ms	84984 KB	Output is correct
10	Correct	451 ms	110256 KB	Output is correct
11	Correct	510 ms	84972 KB	Output is correct
12	Correct	451 ms	110336 KB	Output is correct
13	Correct	516 ms	85032 KB	Output is correct
14	Correct	453 ms	110196 KB	Output is correct
15	Correct	280 ms	87456 KB	Output is correct
16	Correct	285 ms	88828 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	329 ms	51256 KB	Output is correct
9	Correct	451 ms	57368 KB	Output is correct
10	Correct	814 ms	70884 KB	Output is correct
11	Correct	2543 ms	202492 KB	Output is correct
12	Correct	2446 ms	195404 KB	Output is correct
13	Correct	2873 ms	212564 KB	Output is correct
14	Correct	300 ms	87424 KB	Output is correct
15	Correct	298 ms	88828 KB	Output is correct
16	Correct	3 ms	852 KB	Output is correct
17	Correct	3 ms	852 KB	Output is correct
18	Correct	3 ms	708 KB	Output is correct
19	Correct	1 ms	596 KB	Output is correct
20	Correct	3655 ms	239792 KB	Output is correct
21	Correct	3191 ms	223260 KB	Output is correct
22	Correct	2355 ms	197476 KB	Output is correct
23	Correct	303 ms	88888 KB	Output is correct
24	Correct	117 ms	19216 KB	Output is correct
25	Correct	133 ms	36316 KB	Output is correct
26	Correct	129 ms	36348 KB	Output is correct
27	Correct	281 ms	87480 KB	Output is correct
28	Correct	289 ms	88936 KB	Output is correct
29	Correct	1 ms	596 KB	Output is correct
30	Correct	2 ms	724 KB	Output is correct
31	Correct	3 ms	840 KB	Output is correct
32	Correct	4 ms	976 KB	Output is correct
33	Correct	974 ms	123060 KB	Output is correct
34	Correct	1862 ms	163608 KB	Output is correct
35	Correct	2759 ms	211812 KB	Output is correct
36	Correct	3894 ms	286604 KB	Output is correct
37	Correct	511 ms	84984 KB	Output is correct
38	Correct	451 ms	110256 KB	Output is correct
39	Correct	510 ms	84972 KB	Output is correct
40	Correct	451 ms	110336 KB	Output is correct
41	Correct	516 ms	85032 KB	Output is correct
42	Correct	453 ms	110196 KB	Output is correct
43	Correct	280 ms	87456 KB	Output is correct
44	Correct	285 ms	88828 KB	Output is correct
45	Correct	142 ms	44944 KB	Output is correct
46	Correct	211 ms	46996 KB	Output is correct
47	Correct	1241 ms	96680 KB	Output is correct
48	Correct	2548 ms	204456 KB	Output is correct
49	Correct	146 ms	36368 KB	Output is correct
50	Correct	135 ms	36348 KB	Output is correct
51	Correct	140 ms	36584 KB	Output is correct
52	Correct	142 ms	36960 KB	Output is correct
53	Correct	143 ms	36932 KB	Output is correct
54	Correct	146 ms	36964 KB	Output is correct