Submission #1223027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223027		onbert	Catfish Farm (IOI22_fish)	C++20	100 / 100	349 ms	26496 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct fish {
    int y, w;
    bool operator < (const fish &b) const {
        return y < b.y;
    }
};

const int maxn = 1e5 + 5, maxN = 4e5 + 5, maxm = 5e5 + 5, INF = 1e16;
int n, m;
vector<fish> a[maxn];

int seg[maxN][2];
void build(int id, int l, int r, int j) {
    if (l == r) {
        if (l == 0 && j == 1) seg[id][j] = 0;
        else seg[id][j] = -INF;
        return;
    }
    int mid = (l+r)/2;
    build(id*2, l, mid, j); build(id*2+1, mid+1, r, j);
    seg[id][j] = max(seg[id*2][j], seg[id*2+1][j]);
}
void update(int id, int l, int r, int target, int val, int j) {
    if (r < target || target < l) return;
    if (l == r) {
        seg[id][j] = max(val, seg[id][j]);
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, target, val, j); update(id*2+1, mid+1, r, target, val, j);
    seg[id][j] = max(seg[id*2][j], seg[id*2+1][j]);
}
int qry(int id, int l, int r, int findl, int findr, int j) {
    if (r < findl || findr < l) return -INF;
    if (findl <= l && r <= findr) return seg[id][j];
    int mid = (l+r)/2;
    return max(qry(id*2, l, mid, findl, findr, j), qry(id*2+1, mid+1, r, findl, findr, j));
}

long long max_weights(int32_t N, int32_t M, vector<int32_t> X, vector<int32_t> Y,
                      vector<int32_t> W) {
    n = N, m = M;
    for (int i=0;i<m;i++) a[X[i] + 1].push_back({Y[i] + 1, W[i]});
    for (int i=1;i<=n+1;i++) {
        a[i].push_back({0, 0});
        if (i != n+1) a[i].push_back({n+1, 0});
        sort(a[i].begin(), a[i].end());
    }

    build(1, 0, n+1, 0);
    build(1, 0, n+1, 1);

    for (int i=1;i<=n+1;i++) {
        int sz = a[i].size();
        int nxt = qry(1, 0, n+1, 0, n+1, 1);
        for (auto [y, w]:a[i]) {
            int cur = qry(1, 0, n+1, 0, y-1, 1) + w;
            update(1, 0, n+1, y, cur, 1);
            // cout << i << " " << y << endl;
            // cout << i << " " << y << " 1 " << cur << endl;
            // cout << seg[y][1] << endl;
        }
        reverse(a[i].begin(), a[i].end());
        for (auto [y, w]:a[i]) {
            int cur = qry(1, 0, n+1, y+1, n+1, 0) + w;
            update(1, 0, n+1, y, cur, 0);
            // if (i == 3 && y == 5 || y == 6) cout << y << " " << cur << endl;
            // cout << i << " " << y << " 0 " << cur << endl;
            // cout << seg[y][0] << endl;
        }
        update(1, 0, n+1, n+1, nxt, 0);
        update(1, 0, n+1, 0, qry(1, 0, n+1, 0, 0, 0), 1);
        // cout << i << endl;
        // for (int j=0;j<=n+1;j++) cout << seg[j][0] << " "; cout << endl;
        // for (int j=0;j<=n+1;j++) cout << seg[j][1] << " "; cout << endl;
    }
    return qry(1, 0, n+1, 0, 0, 0);


}

• 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