제출 #572470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572470		sidon	Team Contest (JOI22_team)	C++17	73 / 100	146 ms	13004 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 DS : set<pair<int, int>> {
	void add(int i, int v) {
		auto f = lower_bound({i+1, -INF});
		if(f != begin() && prev(f)->second >= v) return;
		f = insert({i, v}).first;
		while(next(f) != end() && next(f)->second <= v)
			erase(next(f));
	}
	int query(int i) {
		auto f = lower_bound({i+1, -INF});
		if(f == begin()) return -INF;
		return prev(f)->second;
	}
};

struct BIT {
	int n;
	vector<DS> a;
	BIT(int N) : n(N), a(N+1) {}
	void update(int i, int j, int v) {
		for(++i; i <= n; i += i&-i) a[i].add(j, v);
	}
	int query(int i, int j) {
		int v = -INF;
		for(++i; i >= 1; i -= i&-i) maxim(v, a[i].query(j));
		return v;
	}
};

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);
	}
	DS f[2];

	for(int i = 0; i < 2; ++i) {
		sort(all(C[i]));
		C[i].erase(unique(all(C[i])), end(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].query(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].query(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].add(sz[k] - 1 - c[i][k], sz[!k] - 1 - c[i][!k]);
		}
	}

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

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

team.cpp: In function 'int main()':
team.cpp:61:13: warning: 'sz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |  BIT b(sz[0]);
      |             ^
team.cpp:65:24: warning: ''target_mem_ref' not supported by dump_expr<expression error>' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |    c[i][k] = sz[k] - 1 - (lower_bound(all(C[k]), a[i][k]) - begin(C[k]));
team.cpp:77:17: warning: '*((void*)& sz +4)' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |    if(j > sz[1] - 1 - c[i][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: 0 / 27