Submission #1158510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158510		Bolatulu	Catfish Farm (IOI22_fish)	C++20	100 / 100	415 ms	59144 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")   
#pragma GCC target("avx,avx2,fma")  
#pragma GCC optimize("unroll-loops") 
#pragma GCC optimize("inline")

#define pb push_back
#define eb emplace_back
#define md ((tl + tr) >> 1)
#define TL v + v, tl, md
#define TR v + v + 1, md + 1, tr
#define all(x) (x).begin(), (x).end()
#define F first
#define S second

using namespace std;

typedef long long ll;

const int N = 3e5 + 7;
const ll INF = 1e18 + 7;  

int n, m;
ll t[2][4 * N], c[2][4 * N], x[N], y[N], w[N], mx[N], dp[N];
vector <pair <int, ll>> v[N], dd[N];
int uc[2][N], u[N], T, Tc[2];

void checkc(int v, int tp) {
    if (uc[tp][v] < Tc[tp]) {
        c[tp][v] = 0;
    }
    uc[tp][v] = Tc[tp];
}

void check(int v) {
    if (u[v] < T) {
        t[0][v] = t[1][v] = -INF;
    }
    u[v] = T;
}

ll get(int tp, int l, int r, int v = 1, int tl = 0, int tr = n) {
    check(v);
    if (tl >= l and tr <= r)
        return t[tp][v];
    if (tl > r or l > tr)
        return -INF;
    return max(get(tp, l, r, TL), get(tp, l, r, TR));
}

ll getc(int tp, int l, int r, int v = 1, int tl = 0, int tr = n) {
    checkc(v, tp);
    if (tl > r or l > tr or c[tp][v] == 0)
        return 0;
    if (tl >= l and tr <= r)
        return c[tp][v];
    return getc(tp, l, r, TL) + getc(tp, l, r, TR);
}

void upd(int tp, int p, ll x, int v = 1, int tl = 0, int tr = n) {
    check(v);
    t[tp][v] = max(t[tp][v], x);
    if (tl == tr)
        return;
    if (p <= md)
        upd(tp, p, x, TL);
    else
        upd(tp, p, x, TR);
}

void updc(int tp, int p, ll x, int v = 1, int tl = 0, int tr = n) {
    checkc(v, tp);
    c[tp][v] += x;
    if (tl == tr)
        return;
    if (p <= md)
        updc(tp, p, x, TL);
    else
        updc(tp, p, x, TR);
}

ll max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
    n = N, m = M;
    bool ok = 1;
    ll s = 0;
    for (int i = 1;i <= m;i++) {
        x[i] = X[i - 1] + 1;
        if (!(x[i] & 1))
            ok = 0;
        y[i] = Y[i - 1] + 1;
        w[i] = W[i - 1];
        s += w[i];
        dd[y[i]].eb(x[i], w[i]);
    }
    for (int i = 1;i <= n;i++) {
        for (auto now : dd[i]) {
            v[now.F].eb(i, now.S);
        }
    }
    if (ok)
        return s;
    vector <array <ll, 3>> vu;
    v[0].eb(n + 1, 0);
    for (int i = 1;i <= n;i++) {
        T = i;
        Tc[i & 1] = i;
        ll s = 0;
        for (auto now : v[i]) {
            s += now.S;
            updc(i & 1, now.F, now.S);
        }
        v[i].eb(n + 1, 0);
        for (int j = v[i - 1].size() - 1;j >= 0;j--) {
            int y = v[i - 1][j].F - 1;
            dp[y] = -INF;
        }
        for (int j = 0;j < vu.size();j++) {
            array <ll, 3> now = vu[j];
            if (now[0] == 0)
                upd(0, now[1], now[2] - getc(!(i & 1), 0, now[1]));
            else {
                ll z = now[2] + getc(i & 1, 0, now[1]);
                dp[now[1]] = max(dp[now[1]], z);
            }
        }   
        vu.clear();
        mx[i] = mx[i - 1];
        int k = 0;
        ll ss = 0;
        for (int j = 0;j < v[i].size();j++) {
            int y = v[i][j].F - 1;
            while (v[i - 1][k].F <= y) {
                ss += v[i - 1][k].S;
                k++;
            }
            ll val = max(ss + get(0, 0, y), mx[i - 1]);
            mx[i] = max(mx[i], val);
            vu.pb({0, y, val});
            vu.pb({1, y, val});
        }
        k = v[i - 1].size() - 1;
        ss = -INF;
        for (int j = v[i].size() - 1;j >= 0;j--) {
            int y = v[i][j].F - 1;
            s -= v[i][j].S;
            while (k >= 0 and v[i - 1][k].F - 1 >= y) {
                ss = max(ss, dp[v[i - 1][k].F - 1]);
                k--;
            }
            ll val = max(ss - s, mx[i - 1]);
            mx[i] = max(mx[i], val);
            vu.pb({1, y, val});
        }
        for (int j = v[i - 1].size() - 1;j >= 0;j--) {
            int y = v[i - 1][j].F - 1;
            ll val = max(dp[y], mx[i - 1]);
            mx[i] = max(mx[i], val);
            vu.pb({0, y, val});
        }
        // cout << mx[i] << ' ';
    }
    return mx[n];
}

// void solve() {
//     int n, m;
//     cin >> n >> m;
//     vector <int> x(m), y(m), w(m);
//     for (int i = 0;i < m;i++)
//         cin >> x[i] >> y[i] >> w[i];
//     cout << max_weights(n, m, x, y, w);
// }

// signed main() {
//     solve();
//     return 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