제출 #544593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544593		pavement	Team Contest (JOI22_team)	C++17	100 / 100	446 ms	51212 KiB

team

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, ans, X[150005], Y[150005], Z[150005], S[150005], dX[150005], dY[150005], dZ[150005], mx[150005], _X[150005], _Y[150005], _Z[150005];
ii ft[150005];
iii T[150005];
vector<int> buffer, vX, vY, vZ;
ordered_set<iii> active_points;

int ls(int x) { return x & -x; }

int ft_qry(int p) {
	ii ret = mp(0, 0);
	for (; p; p -= ls(p)) ret = max(ret, ft[p]);
	return ret.second;
}

void ft_upd(int p, int v) {
	for (; p <= vY.size(); p += ls(p)) ft[p] = max(ft[p], mp(Z[v], v));
}

struct node {
	node *left, *right;
	int S, E, val;
	node(int _s, int _e) : S(_s), E(_e), val(-1e9) {
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	void upd(int p, int v) {
		if (S == E) {
			val = v;
			return;
		}
		int M = (S + E) >> 1;
		if (p <= M) left->upd(p, v);
		else right->upd(p, v);
		val = max(left->val, right->val);
	}
	int qry(int l, int r) {
		if (l > E || r < S) return -1e9;
		if (l <= S && E <= r) return val;
		return max(left->qry(l, r), right->qry(l, r));
	}
} *root;

void remove_point(int x) {
	root->upd(dY[x], -1e9);
}

void add_point(int x) {
	if (mx[dY[x]] >= dZ[S[x]]) return;
	mx[dY[x]] = dZ[S[x]];
	vector<ordered_set<iii>::iterator> to_del;
	// add point (dY[x], dZ[S[x]]) with value Y[x] + Z[S[x]]
	auto it = active_points.upper_bound(mt(dY[x], (int)1e9, (int)1e9));
	if (it != active_points.end() && g1(*it) >= dZ[S[x]]) return;
	while (it != active_points.begin()) {
		--it;
		if (g1(*it) <= dZ[S[x]]) {
			remove_point(g2(*it));
			to_del.pb(it);
		} else break;
	}
	for (auto i : to_del) active_points.erase(i);
	root->upd(dY[x], Y[x] + Z[S[x]]);
	active_points.insert(mt(dY[x], dZ[S[x]], x));
}

void solve() {
	memset(X, 0, sizeof X);
	memset(Y, 0, sizeof Y);
	memset(Z, 0, sizeof Z);
	memset(S, 0, sizeof S);
	memset(dX, 0, sizeof dX);
	memset(dY, 0, sizeof dY);
	memset(dZ, 0, sizeof dZ);
	memset(mx, 0, sizeof mx);
	for (int i = 0; i < 150005; i++) {
		ft[i] = mp(0, 0);
		T[i] = mt(0, 0, 0);
	}
	buffer.clear();
	vX.clear();
	vY.clear();
	vZ.clear();
	active_points.clear();
	for (int i = 1; i <= N; i++) {
		X[i] = _X[i];
		Y[i] = _Y[i];
		Z[i] = _Z[i];
		T[i] = mt(X[i], Y[i], Z[i]);
		vX.pb(X[i]);
		vY.pb(Y[i]);
		vZ.pb(Z[i]);
	}
	sort(vX.begin(), vX.end());
	vX.erase(unique(vX.begin(), vX.end()), vX.end());
	sort(vY.begin(), vY.end());
	vY.erase(unique(vY.begin(), vY.end()), vY.end());
	sort(vZ.begin(), vZ.end());
	vZ.erase(unique(vZ.begin(), vZ.end()), vZ.end());
	sort(T + 1, T + 1 + N);
	for (int i = 1; i <= N; i++) {
		tie(X[i], Y[i], Z[i]) = T[i];
		dX[i] = lower_bound(vX.begin(), vX.end(), X[i]) - vX.begin() + 1;
		dY[i] = lower_bound(vY.begin(), vY.end(), Y[i]) - vY.begin() + 1;
		dZ[i] = lower_bound(vZ.begin(), vZ.end(), Z[i]) - vZ.begin() + 1;
	}
	root = new node(1, N);
	for (int i = 1; i <= N; i++) {
		if (X[i] > X[i - 1]) {
			for (int j : buffer) add_point(j);
			buffer.clear();
		}
		int lo = 0, hi = (int)active_points.size() - 1, lb = -1;
		while (lo <= hi) {
			int mid = (lo + hi) >> 1;
			if (g0(*active_points.find_by_order(mid)) > dY[i]) lb = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		lo = 0, hi = (int)active_points.size() - 1;
		int rb = -1;
		while (lo <= hi) {
			int mid = (lo + hi) >> 1;
			if (g1(*active_points.find_by_order(mid)) > dZ[i]) rb = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		if (lb != -1 && rb != -1)
			ans = max(ans, X[i] + root->qry(g0(*active_points.find_by_order(lb)), g0(*active_points.find_by_order(rb))));
		S[i] = ft_qry(dY[i] - 1);
		ft_upd(dY[i], i);
		if (Z[S[i]] > Z[i]) buffer.pb(i);
	}
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> _X[i] >> _Y[i] >> _Z[i];
	solve();
	for (int i = 1; i <= N; i++) swap(_Y[i], _Z[i]);
	solve();
	cout << (ans == 0 ? -1 : ans) << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

team.cpp: In function 'void ft_upd(long long int, long long int)':
team.cpp:44:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (; p <= vY.size(); p += ls(p)) ft[p] = max(ft[p], mp(Z[v], v));
      |         ~~^~~~~~~~~~~~
team.cpp: At global scope:
team.cpp:163:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  163 | main() {
      | ^~~~

• 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