Submission #549263

#	Time	Username	Problem	Language	Result	Execution time	Memory
549263		nonsensenonsense1	Team Contest (JOI22_team)	C++17	100 / 100	1928 ms	85492 KiB

team

#include <cstdio>
#include <vector>
#include <algorithm>

inline void mxm(int &a, int b) {
	a = std::max(a, b);
}

const int N = 150000;
int n, yval[N], zval[N], amt, zamt, y1[N], z1[N], y2[N], z2[N];
std::pair<int, std::pair<int, int> > a[N];
std::vector<int> val[N * 2], t[N * 2];

void show(int i, int j) {
	for (i += amt; i; i >>= 1) val[i].push_back(j);
}

void build() {
	for (int i = 2 * amt - 1; i; --i) {
		if (i < amt) {
			val[i].resize(val[i << 1].size() + val[i << 1 | 1].size());
			std::merge(val[i << 1].begin(), val[i << 1].end(), val[i << 1 | 1].begin(), val[i << 1 | 1].end(), val[i].begin());
		} else std::sort(val[i].begin(), val[i].end());
		val[i].resize(std::unique(val[i].begin(), val[i].end()) - val[i].begin());
		t[i].resize(val[i].size() * 2);
	}
}

int find(int i, int j) {
	return std::lower_bound(val[i].begin(), val[i].end(), j) - val[i].begin();
}

void update1(int i, int j, int x) {
	for (j += val[i].size(); j; j >>= 1) mxm(t[i][j], x);
}

void update(int i, int j, int x) {
	for (i += amt; i; i >>= 1) update1(i, find(i, j), x);
}

int query1(int i, int lj, int rj) {
	lj = find(i, lj);
	rj = find(i, rj);
	int ans = 0;
	for (lj += val[i].size(), rj += val[i].size(); lj < rj; lj >>= 1, rj >>= 1) {
		if (lj & 1) mxm(ans, t[i][lj++]);
		if (rj & 1) mxm(ans, t[i][--rj]);
	}
	return ans;
}

int query(int li, int ri, int lj, int rj) {
	int ans = 0;
	for (li += amt, ri += amt; li < ri; li >>= 1, ri >>= 1) {
		if (li & 1) mxm(ans, query1(li++, lj, rj));
		if (ri & 1) mxm(ans, query1(--ri, lj, rj));
	}
	return ans;
}

struct tree {
	int n;
	std::vector<int> t;
	void resize(int n_) {
		n = n_;
		t.assign(2 * n, 0);
	}
	void update(int i, int x) {
		for (i += n; i; i >>= 1) mxm(t[i], x);
	}
	int query(int l, int r) {
		int ans = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) mxm(ans, t[l++]);
			if (r & 1) mxm(ans, t[--r]);
		}
		return ans;
	}
} tr;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d%d", &a[i].first, &a[i].second.first, &a[i].second.second);
		yval[i] = a[i].second.first;
		zval[i] = a[i].second.second;
	}
	std::sort(yval, yval + n);
	std::sort(zval, zval + n);
	amt = std::unique(yval, yval + n) - yval;
	zamt = std::unique(zval, zval + n) - zval;
	std::sort(a, a + n);
	tr.resize(amt);
	for (int i = 0; i < n; ++i) {
		a[i].second.first = std::lower_bound(yval, yval + amt, a[i].second.first) - yval;
		y1[i] = a[i].second.first + 1;
		z1[i] = tr.query(0, a[i].second.first);
		if (z1[i] <= a[i].second.second) z1[i] = 0;
		tr.update(a[i].second.first, a[i].second.second);
	}
	tr.resize(zamt);
	for (int i = 0; i < n; ++i) {
		int p = std::lower_bound(zval, zval + zamt, a[i].second.second) - zval;
		y2[i] = tr.query(0, p);
		z2[i] = a[i].second.second;
		if (y2[i] - 1 <= a[i].second.first) y2[i] = 0;
		tr.update(p, a[i].second.first + 1);
	}
	for (int i = 0; i < n; ++i) {
		if (y1[i] && z1[i]) show(y1[i] - 1, z1[i]);
		if (y2[i] && z2[i]) show(y2[i] - 1, z2[i]);
	}
	build();
	int ans = 0;
	for (int i = 0; i < n;) {
		int j = i;
		do {
			int x = query(a[i].second.first + 1, amt, a[i].second.second + 1, ~(1 << 31));
			if (x) ans = std::max(ans, a[i].first + x);
			++i;
		} while (i < n && a[i].first == a[i - 1].first);
		for (; j < i; ++j) {
			if (y1[j] && z1[j]) update(y1[j] - 1, z1[j], yval[y1[j] - 1] + z1[j]);
			if (y2[j] && z2[j]) update(y2[j] - 1, z2[j], yval[y2[j] - 1] + z2[j]);
		}
	}
	printf("%d\n", ans ? ans : -1);
	return 0;
}

Compilation message (stderr)

team.cpp: In function 'int main()':
team.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
team.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d%d%d", &a[i].first, &a[i].second.first, &a[i].second.second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27