Submission #969654

#	Time	Username	Problem	Language	Result	Execution time	Memory
969654		vjudge1	Catfish Farm (IOI22_fish)	C++17	100 / 100	518 ms	43360 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>
using namespace std;

const int64_t inf = 1e18;

class segtree_t {
   public:
    segtree_t *left, *right;
    int l, r, m;
    int64_t val;

    segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val(-inf) {
        if (l == r) return;
        left = new segtree_t(l, m);
        right = new segtree_t(m + 1, r);
    }

    void Update(int s, int t, int64_t x) {
        if (r < s || l > t) return;
        if (s <= l && r <= t) {
            val = max(val, x);
            return;
        }
        left->Update(s, t, x);
        right->Update(s, t, x);
    }

    int64_t Get(int p) {
        if (l == r) return val;
        if (p <= m) return max(val, left->Get(p));
        return max(val, right->Get(p));
    }
};

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    vector<int64_t> sum(N);
    vector<int> aback(N);
    for (int i = 0; i < M; i++) {
        sum[X[i]] += W[i];
        if (Y[i] == N - 1) aback[X[i]] = W[i];
    }

    const int64_t inf = 1e18;
    vector<vector<pair<int, int>>> event(N);
    for (int i = 0; i < M; i++) {
        event[X[i]].emplace_back(Y[i], W[i]);
    }
    for (int i = 0; i < N; i++) {
        event[i].emplace_back(0, 0);
        event[i].emplace_back(N - 2, 0);
        sort(event[i].begin(), event[i].end());
    }
    segtree_t *tree0 = new segtree_t(0, N);
    segtree_t *tree1 = new segtree_t(0, N);
    tree0->Update(0, N, 0);
    tree1->Update(N, N, 0);

    for (int i = 0; i < N; i++) {
        if (i + 1 < N) {
            for (auto [y, w] : event[i]) {
                tree0->Update(y + 1, N, tree0->Get(y) + w);
            }
        }
        reverse(event[i].begin(), event[i].end());
        if (i > 0) {
            for (auto [y, w] : event[i]) {
                if (y == N - 1) continue;
                tree1->Update(0, y, tree1->Get(y + 1) + w);
            }
        }
        if (i == 1) tree0->Update(0, 0, sum[0]);
        if (i + 2 < N) tree0->Update(0, 0, tree1->Get(0));
        if (i == N - 1) break;
        int64_t dpN1 = tree1->Get(N);
        int64_t dp01 = tree1->Get(0);
        tree1->Update(N, N, max(tree0->Get(N), tree0->Get(0)));
        if (i + 1 == N - 1) tree0->Update(N, N, tree0->Get(0) + sum[N - 1]);
        tree1->Update(N - 1, N - 1, dpN1 + aback[i + 1]);
        tree0->Update(0, 0, dp01);
    }

    return max(tree1->Get(0), max(tree0->Get(N), tree1->Get(N)));
}

Compilation message (stderr)

fish.cpp: In constructor 'segtree_t::segtree_t(int, int)':
fish.cpp:14:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |     segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val(-inf) {
      |                                             ~~^~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:46:19: warning: unused variable 'inf' [-Wunused-variable]
   46 |     const int64_t inf = 1e18;
      |                   ^~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16