Submission #49838

#	Time	Username	Problem	Language	Result	Execution time	Memory
49838		Noam527	New Home (APIO18_new_home)	C++17	57 / 100	5065 ms	116524 KiB

new_home

#include <bits/stdc++.h>
#include <unordered_map>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
#define yesno(X) cout << ((X) ? "YES" : "NO") << endl
#define noyes(X) cout << ((X) ? "NO" : "YES") << endl
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

const int lim = 1e8;

struct segtree {
	int n, rtn;
	vector<int> tree;
	segtree(int size = 1) {
		n = max(2, size);
		tree.resize(2 * n, -inf);
	}
	void fix(int pos) {
		tree[pos] = max(tree[2 * pos + 1], tree[2 * pos + 2]);
	}
	void upd(int pos, int val) {
		tree[pos += n - 1] = val;
		pos = (pos - 1) / 2;
		while (pos > 0) {
			fix(pos);
			pos = (pos - 1) / 2;
		}
		fix(0);
	}
	int query(int l, int r) {
		rtn = -inf;
		for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) {
			if (!(l & 1)) rtn = max(rtn, tree[l++]);
			if (r & 1) rtn = max(rtn, tree[r--]);
		}
		if (l == r) rtn = max(rtn, tree[l]);
		return rtn;

	}
	void show() {
		for (int i = n - 1; i < 2 * n - 1; i++) cout << tree[i] << " "; cout << endl;
	}
};

struct line {
	int x, h;
	line(int xx = 0, int hh = 0, bool inc = true) {
		x = xx;
		if (inc)
			h = hh - xx;
		else
			h = hh + xx;
	}
	bool operator < (const line &a) const {
		if (x != a.x) return x < a.x;
		return h < a.h;
	}
	ll operator () () {
		return 5LL * lim * x + h;
	}
	bool operator == (const line &a) const {
		return x == a.x && h == a.h;
	}
};

struct query {
	int l, y, ind;
	query(int ll = 0, int yy = 0, int ii = 0) {
		l = ll;
		y = yy;
		ind = ii;
	}
	bool operator < (const query &a) const {
		return y < a.y;
	}
};

struct eve {
	int x, type, when, operation; // insert -> operation == 0
	eve(int xx = 0, int tt = 0, int ww = 0, int oo = 0) {
		x = xx;
		type = tt;
		when = ww;
		operation = oo;
	}
	bool operator < (const eve &a) const {
		return when < a.when;
	}
};

int n, k, q, p[4];
vector<eve> E;
vector<query> Q;
vector<line> incl, decl;
vector<multiset<int>> active;
segtree I, D;

struct linehash {
	ll operator () (const line &a) const {
		return 5LL * lim * a.x + a.h;
	}
};

unordered_map<line, int, linehash> incin, decin;
unordered_map<line, int, linehash> ince, dece;

vector<pair<ll, int>> IN1, IN2, OUT1, OUT2;

vector<int> answer;

// last value at most f.l
int decsearch(const query &f) {
	static int lo, hi, mid;
	lo = 0, hi = (int)decl.size() - 1;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (decl[mid].x <= f.l) lo = mid;
		else hi = mid - 1;
	}
	if (decl[lo].x > f.l) lo--;
	return lo;
}
// first value at least f.l
int incsearch(const query &f) {
	static int lo, hi, mid;
	lo = 0, hi = (int)incl.size() - 1;
	while (lo < hi) {
		mid = (lo + hi) / 2;
		if (incl[mid].x < f.l) lo = mid + 1;
		else hi = mid;
	}
	if (incl[lo].x < f.l) lo++;
	return lo;
}
int AT(vector<pair<ll, int>> &AA, ll val) {
	static int lo, hi, mid;
	lo = 0, hi = AA.size() - 1;
	while (lo < hi) {
		mid = (lo + hi) / 2;
		if (AA[mid].first < val) lo = mid + 1;
		else hi = mid;
	}
	++AA[lo].second;
	return AA[lo].second - 1;
}
multiset<int>::iterator it, nit, pit;

int main() {

//	time_t aaaa = clock();
	//	int tot = 0, tot2 = 0;
	//	cin >> n >> k >> q;
	scanf("%d%d%d", &n, &k, &q);
	active.resize(k);
	answer.resize(q);
	for (int i = 0; i < n; i++) {
		//		cin >> p[0] >> p[1] >> p[2] >> p[3];
		scanf("%d%d%d%d", &p[0], &p[1], &p[2], &p[3]);
		p[1]--;
		E.push_back(eve(p[0], p[1], p[2], 0));
		E.push_back(eve(p[0], p[1], p[3] + 1, 1));
	}
	for (int i = 0; i < q; i++) {
		//		cin >> p[0] >> p[1];
		scanf("%d%d", &p[0], &p[1]);
		Q.push_back(query(p[0], p[1], i));
	}
	sort(E.begin(), E.end());
	sort(Q.begin(), Q.end());
	for (const auto &i : E) {
		if (i.operation == 0) {
			it = active[i.type].insert(i.x);


			if (next(it) != active[i.type].end()) {
				nit = next(it);
				decl.push_back(line((*it + *nit + 1) / 2, (*nit - *it) / 2, false));
				incl.push_back(line((*it + *nit) / 2, (*nit - *it) / 2, true));
			}
			else {
				incl.push_back(line(lim, lim - *it, true));
			}
			if (it != active[i.type].begin()) {
				pit = prev(it);
				decl.push_back(line((*it + *pit + 1) / 2, (*it - *pit) / 2, false));
				incl.push_back(line((*it + *pit) / 2, (*it - *pit) / 2, true));
			}
			else {
				decl.push_back(line(0, *it, false));
			}
		}
		else {
			active[i.type].erase(active[i.type].find(i.x));
			it = active[i.type].lower_bound(i.x);
			if (active[i.type].size()) {
				if (it == active[i.type].end()) {
					--it;
					incl.push_back(line(lim, lim - *it, true));
				}
				else if (it == active[i.type].begin()) {
					decl.push_back(line(0, *it, false));
				}
				else {
					pit = prev(it);
					decl.push_back(line((*it + *pit + 1) / 2, (*it - *pit) / 2, false));
					incl.push_back(line((*it + *pit) / 2, (*it - *pit) / 2, true));
				}
			}
		}
	}
	for (auto &i : active) i.clear();
	sort(incl.begin(), incl.end());
	sort(decl.begin(), decl.end());
	I = segtree(incl.size());
	D = segtree(decl.size());
//	for (int i = incl.size() - 1; i >= 0; i--)
//		incin[incl[i]] = ince[incl[i]] = i;
//	for (int i = decl.size() - 1; i >= 0; i--)
//		decin[decl[i]] = dece[decl[i]] = i;

	for (int i = incl.size() - 1; i >= 0; i--) {
		if (IN1.empty() || incl[i]() != IN1.back().first)
			IN1.emplace_back(incl[i](), i);
		IN1.back().second = i;
	}
	for (int i = decl.size() - 1; i >= 0; i--) {
		if (IN2.empty() || decl[i]() != IN2.back().first)
			IN2.emplace_back(decl[i](), i);
		IN2.back().second = i;
	}
	reverse(IN1.begin(), IN1.end());
	reverse(IN2.begin(), IN2.end());
	OUT1 = IN1;
	OUT2 = IN2;
	//	cout << "number of increasing lines: " << incl.size() << endl;
	//	for (const auto &i : incl) cout << i.x << " "; cout << endl;
	//	cout << "number of decreasing lines: " << decl.size() << endl;
	//	for (const auto &i : decl) cout << i.x << " "; cout << endl;
	int cnt = 0, nxt = 0;
	line l;
	for (const auto &f : Q) {
		while (nxt < E.size() && E[nxt].when <= f.y) {
			auto i = E[nxt];

			if (i.operation == 0) {
				it = active[i.type].insert(i.x);
				if (active[i.type].size() == 1) cnt++;

				// add
				if (next(it) != active[i.type].end()) {
					nit = next(it);
					l = line((*it + *nit + 1) / 2, (*nit - *it) / 2, false);
					D.upd(AT(IN2, l()), l.h);
					l = line((*it + *nit) / 2, (*nit - *it) / 2, true);
					I.upd(AT(IN1, l()), l.h);
				}
				else {
					l = line(lim, lim - *it, true);
					I.upd(AT(IN1, l()), l.h);
				}

				if (it != active[i.type].begin()) {
					pit = prev(it);
					l = line((*it + *pit + 1) / 2, (*it - *pit) / 2, false);
					D.upd(AT(IN2, l()), l.h);
					l = line((*it + *pit) / 2, (*it - *pit) / 2, true);
					I.upd(AT(IN1, l()), l.h);
				}
				else {
					l = line(0, *it, false);
					D.upd(AT(IN2, l()), l.h);
				}

				// erase
				if (next(it) == active[i.type].end()) {
					if (it != active[i.type].begin()) {
						--it;
						l = line(lim, lim - *it, true);
						I.upd(AT(OUT1, l()), -inf);
						++it;
					}
				}
				else {
					if (it == active[i.type].begin()) {
						++it;
						l = line(0, *it, false);
						D.upd(AT(OUT2, l()), -inf);
						--it;
					}
					else {
						nit = pit = it, nit++, pit--;
						l = line((*nit + *pit + 1) / 2, (*nit - *pit) / 2, false);
						D.upd(AT(OUT2, l()), -inf);
						l = line((*nit + *pit) / 2, (*nit - *pit) / 2, true);
						I.upd(AT(OUT1, l()), -inf);
					}
				}
			}
			else {
				it = active[i.type].find(i.x);
				if (next(it) != active[i.type].end()) {
					nit = next(it);
					l = line((*it + *nit + 1) / 2, (*nit - *it) / 2, false);
					D.upd(AT(OUT2, l()), -inf);
					l = line((*it + *nit) / 2, (*nit - *it) / 2, true);
					I.upd(AT(OUT1, l()), -inf);
				}
				else {
					l = line(lim, lim - *it, true);
					I.upd(AT(OUT1, l()), -inf);
				}

				if (it != active[i.type].begin()) {
					pit = prev(it);
					l = line((*it + *pit + 1) / 2, (*it - *pit) / 2, false);
					D.upd(AT(OUT2, l()), -inf);
					l = line((*it + *pit) / 2, (*it - *pit) / 2, true);
					I.upd(AT(OUT1, l()), -inf);
				}
				else {
					l = line(0, *it, false);
					D.upd(AT(OUT2, l()), -inf);
				}

				active[i.type].erase(active[i.type].find(i.x));
				it = active[i.type].lower_bound(i.x);
				if (active[i.type].size()) {
					if (it == active[i.type].end()) {
						--it;
						l = line(lim, lim - *it, true);
						I.upd(AT(IN1, l()), l.h);
						++it;
					}
					else if (it == active[i.type].begin()) {
						l = line(0, *it, false);
						D.upd(AT(IN2, l()), l.h);
					}
					else {
						pit = prev(it);
						l = line((*it + *pit + 1) / 2, (*it - *pit) / 2, false);
						D.upd(AT(IN2, l()), l.h);
						l = line((*it + *pit) / 2, (*it - *pit) / 2, true);
						I.upd(AT(IN1, l()), l.h);
					}
				}
				else cnt--;
			}
			nxt++;
		}
		// query
		//		cout << "checking query " << f.l << " " << f.y << endl;
		//		cout << "a total of active: " << cnt << endl;
		if (cnt < k) answer[f.ind] = -1;
		else {
			int mx = -inf;
			int i1 = incsearch(f);
			int i2 = decsearch(f);
			//			cout << "i1 i2 " << i1 << " " << i2 << endl;
			if (0 <= i1 && i1 < incl.size()) mx = max(mx, I.query(i1, incl.size() - 1) + f.l);
			//			I.show();
			//			cout << I.query(i1, incl.size() - 1) << endl;
			if (0 <= i2 && i2 < decl.size()) mx = max(mx, D.query(0, i2) - f.l);
			//			D.show();
			//			cout << D.query(0, i2) << endl;
			answer[f.ind] = mx;
		}
	}
	for (const auto &i : answer) printf("%d\n", i);
	//	cout << "time wasted on updating: " << tot << endl;
	//	cout << "time wasted on querying: " << tot2 << endl;
//	cout << clock() - aaaa << endl;
}

Compilation message (stderr)

new_home.cpp: In member function 'void segtree::show()':
new_home.cpp:49:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = n - 1; i < 2 * n - 1; i++) cout << tree[i] << " "; cout << endl;
   ^~~
new_home.cpp:49:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = n - 1; i < 2 * n - 1; i++) cout << tree[i] << " "; cout << endl;
                                                                   ^~~~
new_home.cpp: In function 'int main()':
new_home.cpp:250:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (nxt < E.size() && E[nxt].when <= f.y) {
          ~~~~^~~~~~~~~~
new_home.cpp:367:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (0 <= i1 && i1 < incl.size()) mx = max(mx, I.query(i1, incl.size() - 1) + f.l);
                   ~~~^~~~~~~~~~~~~
new_home.cpp:370:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (0 <= i2 && i2 < decl.size()) mx = max(mx, D.query(0, i2) - f.l);
                   ~~~^~~~~~~~~~~~~
new_home.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:166:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &p[0], &p[1], &p[2], &p[3]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:173:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &p[0], &p[1]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 20