Submission #544597

#	Time	Username	Problem	Language	Result	Execution time	Memory
544597		sidon	Team Contest (JOI22_team)	C++17	100 / 100	1962 ms	278544 KiB

team

#include <bits/stdc++.h>
using namespace std;
#define maxim(X, Y) (X = max(X, Y))
#define all(X) begin(X), end(X)

const int INF = 2e9+5;

struct Fenwick {
	int n, *a;
	Fenwick(int N) : n(N), a(new int[N+1]) {
		fill(a, a + N + 1, -INF);
	}
	void upd(int i, int v) {
		for(++i; i <= n; i += i&-i) maxim(a[i], v);
	}
	int qry(int i) {
		int v = -INF;
		for(++i; i >= 1; i -= i&-i) maxim(v, a[i]);
		return v;
	}
};

int sI, sV;
struct ST {
#define m ((l + r) / 2)
	int v;
	ST *L = NULL, *R = NULL;
	ST() : v(-INF) {};
	void upd(int i, int val) {
		sI = i, sV = val;
		_upd(0, 1<<18);
	}
	void _upd(int l, int  r) {
		maxim(v, sV);
		if(r - l > 1) {
			if(sI < m) (L ? : L = new ST)->_upd(l, m);
			if(sI >=m) (R ? : R = new ST)->_upd(m, r);
		}
	}
	int qry(int i) {
		sI = i + 1, sV = -INF;
		return qry(0, 1<<18), sV;
	}
	void qry(int l, int r) {
		if(r <= sI) return void(maxim(sV, v));
		if(l < sI) {
			if(L) L->qry(l, m);
			if(R) R->qry(m, r);
		}
	}
};

struct BIT {
	int n;
	vector<ST*> a;
	BIT(int N) : n(N), a(N+1) {
		for(auto &i : a) i = new ST;
	}
	void update(int i, int j, int v) {
		for(++i; i <= n; i += i&-i) a[i]->upd(j, v);
	}
	int query(int i, int j) {
		sI = j + 1, sV = -INF;
		for(++i; i >= 1; i -= i&-i) a[i]->qry(0, 1<<18);
		return sV;
	}
};

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	int N; cin >> N;
	array<int, 3> a[N];
	vector<int> C[2];
	array<int, 2> sz, c[N];

	for(auto &[x, y, z] : a) {
		cin >> x >> y >> z;
		C[0].push_back(x);
		C[1].push_back(y);
	}
	Fenwick *f[2];

	for(int i = 0; i < 2; ++i) {
		sort(all(C[i]));
		C[i].erase(unique(all(C[i])), end(C[i]));
		f[i] = new Fenwick(sz[i] = size(C[i]));
	}

	sort(a, a + N, [&](const auto &i, const auto &j) {
		return i[2] < j[2];
	});

	BIT b(sz[0]);

	for(int i = 0; i < N; ++i)
		for(int k = 0; k < 2; ++k)
			c[i][k] = sz[k] - 1 - (lower_bound(all(C[k]), a[i][k]) - begin(C[k]));

	int ans = -INF;

	for(int l = 0, r; l < N; l = r) {
		for(r = l + 1; r < N && a[l][2] == a[r][2]; ++r);

		for(int i = l; i < r; ++i)
			maxim(ans, a[i][2] + b.query(c[i][0] - 1, c[i][1] - 1));

		for(int i = l; i < r; ++i) {
			int j = f[0]->qry(sz[0] - 2 - c[i][0]);
			if(j > sz[1] - 1 - c[i][1])
				b.update(c[i][0], sz[1] - 1 - j, a[i][0] + C[1][j]);

			j = f[1]->qry(sz[1] - 2 - c[i][1]);
			if(j > sz[0] - 1 - c[i][0])
				b.update(sz[0] - 1 - j, c[i][1], a[i][1] + C[0][j]);

			for(int k = 0; k < 2; ++k)
				f[k]->upd(sz[k] - 1 - c[i][k], sz[!k] - 1 - c[i][!k]);
		}
	}

	cout << max(ans, int(-1));
}

• 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