10167번 - 금광

C++17

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

using i64 = long long;

template<typename NodeType, typename F_Merge>
struct SegTree { // 1-indexed
public:
	using A = NodeType;
	SegTree() : SegTree(0, A()) {}
	explicit SegTree(int n, const A& e) : n(n), lg(Log2(n)), sz(1 << lg), e(e), tree(sz << 1, e) {}
	void Set(int i, const A& val) { tree[--i | sz] = val; }
	void Init() { for (int i = sz - 1; i; i--) tree[i] = M(tree[i << 1], tree[i << 1 | 1]); }
	void Update(int i, const A& val) {
		tree[--i |= sz] = val;
		while (i >>= 1) tree[i] = M(tree[i << 1], tree[i << 1 | 1]);
	}
    A Query(int i) const { return tree[--i | sz]; }
	A Query(int l, int r) const {
		A L = e, R = e;
		for (--l |= sz, --r |= sz; l <= r; l >>= 1, r >>= 1) {
			if (l & 1) L = M(L, tree[l++]);
			if (~r & 1) R = M(tree[r--], R);
		}
		return M(L, R);
	}
private:
	const int n, lg, sz; const A e;
	vector<A> tree;
	F_Merge M;
	static int Log2(int n) {
		int ret = 0;
		while (n > 1 << ret) ret++;
		return ret;
	}
};

struct Info { int x, y, val; };

struct Node {
    i64 sum, l, r, mx;
    Node() : Node(0) {}
    constexpr Node(i64 val) : sum(val), l(val), r(val), mx(val) {}
    bool operator== (const Node& i) const {
        return sum == i.sum && l == i.l && r == i.r && mx == i.mx;
    }
};

constexpr Node e(-1e18);

struct F_Merge {
    Node operator() (const Node& a, const Node& b) const {
        if (a == e) return b;
        if (b == e) return a;
        Node ret;
        ret.sum = a.sum + b.sum;
        ret.l = max(a.l, a.sum + b.l);
        ret.r = max(a.r + b.sum, b.r);
        ret.mx = max({ a.mx, b.mx, a.r + b.l });
        return ret;
    }
};

int main() {
    fastio;
    // 1. input
    int n; cin >> n;
    vector<Info> v(n); vector<int> I;
    for (auto& [x, y, val] : v) {
        cin >> x >> y >> val;
        I.push_back(x);
    }

    // 2. coordinate compression
    sort(I.begin(), I.end()), I.erase(unique(I.begin(), I.end()), I.end());
    for (auto& [x, y, val] : v) x = lower_bound(I.begin(), I.end(), x) - I.begin() + 1;
    sort(v.begin(), v.end(), [](const Info& a, const Info& b) { return a.y < b.y; });

    // 3. sweeping
    i64 res = 0;
	SegTree<Node, F_Merge> ST(I.size(), e);
    for (int i = 0; i < n; i++) {
        if (i && v[i - 1].y == v[i].y) continue;
        for (int i = 1; i <= I.size(); i++) ST.Set(i, Node());
        ST.Init();
        for (int j = i; j < n; j++) {
            ST.Update(v[j].x, Node(ST.Query(v[j].x).mx + v[j].val));
            if (j == n - 1 || v[j].y != v[j + 1].y) res = max(res, ST.Query(1, I.size()).mx);
        }
    }
    cout << res << '\n';
}
결과	메모리	시간	코드 길이
100점	2444	512	2659
문제

문제

출처

ICPC

C++17

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
