Submission #547415

#	Time	Username	Problem	Language	Result	Execution time	Memory
547415		skittles1412	Team Contest (JOI22_team)	C++17	100 / 100	1826 ms	190480 KiB

team

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 150'005;

struct DS1 {
	set<pair<int, int>> s;

	void insert(int x, int y) {
		auto it = s.upper_bound({x, 0});
		if (it != s.begin()) {
			if (prev(it)->second >= y) {
				return;
			}
		}
		while (it != s.end() && y >= it->second) {
			it = s.erase(it);
		}
		s.emplace_hint(it, x, y);
	}

	int query(int x) const {
		auto it = s.lower_bound({x, 0});
		if (it == s.begin()) {
			return -1;
		}
		return (--it)->second;
	}
};

struct DS2 {
	DS1 ds;

	void insert(int x, int y) {
		ds.insert(y, x);
	}

	int query(int y) const {
		return ds.query(y);
	}
};

struct chash {
	uint64_t operator()(uint64_t x) const {
		x ^= x << 11;
		x ^= x >> 9;
		x ^= x >> 7;
		return x;
	}
};

struct Bit1 {
	__gnu_pbds::gp_hash_table<int, int, chash> v;

	void insert(int ind, int x) {
		ind++;
		while (ind <= maxn) {
			v[ind] = max(v[ind], x);
			ind += ind & -ind;
		}
	}

	int query(int ind) const {
		int ans = -1;
		while (ind) {
			auto it = v.find(ind);
			if (it != v.end()) {
				ans = max(ans, it->second);
			}
			ind -= ind & -ind;
		}
		return ans;
	}
};

struct DS3 {
	Bit1 v[maxn + 1];

	void insert(int ind, int y, int val) {
		ind = maxn - ind;
		y = maxn - y;
		ind++;
		while (ind <= maxn) {
			v[ind].insert(y, val);
			ind += ind & -ind;
		}
	}

	int query(int ind, int y) const {
		ind = maxn - ind;
		y = maxn - y;
		int ans = -1;
		while (ind) {
			ans = max(ans, v[ind].query(y));
			ind -= ind & -ind;
		}
		return ans;
	}
};

struct Comp {
	vector<int> comp;

	Comp(int n, array<int, 3> arr[], int ind) : comp(n) {
		for (int i = 0; i < n; i++) {
			comp[i] = arr[i][ind];
		}
		sort(begin(comp), end(comp));
		comp.erase(unique(begin(comp), end(comp)), comp.end());
	}

	int operator[](int ind) const {
		return int(lower_bound(begin(comp), end(comp), ind) - comp.begin());
	}
};

DS1 ds1;
DS2 ds2;
DS3 ds3;

void solve() {
	int n;
	cin >> n;
	array<int, 3> arr[n];
	for (auto& [x, y, z] : arr) {
		cin >> x >> y >> z;
	}
	sort(arr, arr + n);
	Comp xs(n, arr, 1), ys(n, arr, 2);
	int ans = -1;
	for (int i = 0; i < n;) {
		int start = i;
		for (; i < n && arr[start][0] == arr[i][0]; i++) {
			auto& [z, x, y] = arr[i];
			int cur = ds3.query(xs[x], ys[y]);
			if (cur != -1) {
				ans = max(ans, z + cur);
			}
		}
		for (int j = start; j < i; j++) {
			auto& [_, x, y] = arr[j];
			int ly = ds1.query(x);
			if (ly > y) {
				ds3.insert(xs[x], ys[ly], x + ly);
			}
			int rx = ds2.query(y);
			if (rx > x) {
				ds3.insert(xs[rx], ys[y], rx + y);
			}
			ds1.insert(x, y);
			ds2.insert(x, y);
		}
	}
	cout << ans << endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

• 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