제출 #1158456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158456		Bolatulu	메기 농장 (IOI22_fish)	C++20	100 / 100	790 ms	47448 KiB

fish

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

#define pb push_back
#define eb emplace_back
#define md (tl + tr) / 2
#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];
vector <pair <int, ll>> v[N];

ll get(int tp, int l, int r, int v = 1, int tl = 0, int tr = n) {
    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) {
    if (tl > r or l > tr)
        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) {
    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) {
    c[tp][v] += x;
    if (tl == tr)
        return;
    if (p <= md)
        updc(tp, p, x, TL);
    else
        updc(tp, p, x, TR);
}

void del(int v = 1, int tl = 0, int tr = n) {
    if (t[0][v] == -INF and t[1][v] == -INF)
        return;
    t[0][v] = -INF;
    t[1][v] = -INF;
    if (tl != tr) {
        del(TL);
        del(TR);
    }
}

void delc(int tp, int v = 1, int tl = 0, int tr = n) {
    if (c[tp][v] == 0)
        return;
    c[tp][v] = 0;
    if (tl != tr) {
        delc(tp, TL);
        delc(tp, TR);
    }
}

ll max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
    n = N, m = M;
    for (int i = 1;i <= m;i++) {
        x[i] = X[i - 1] + 1;
        y[i] = Y[i - 1] + 1;
        w[i] = W[i - 1];
        v[x[i]].eb(y[i], w[i]);
    }
    vector <array <ll, 3>> vu;
    for (int i = 1;i <= n;i++) {
        sort(all(v[i]));
        delc(i & 1);
        for (auto now : v[i]) {
            updc(i & 1, now.F, now.S);
        }
        v[i].eb(n + 1, 0);
        del();
        for (auto now : vu) {
            if (now[0] == 0)
                upd(0, now[1], now[2] - getc(!(i & 1), 0, now[1]));
            else
                upd(1, now[1], now[2] + getc(i & 1, 0, now[1]));
        }
        vu.clear();
        mx[i] = mx[i - 1];
        for (int j = 0;j < v[i].size();j++) {
            int y = v[i][j].F - 1;
            ll val = max(getc(!(i & 1), 0, y) + get(0, 0, y), mx[i - 1]);
            mx[i] = max(mx[i], val);
            vu.pb({0, y, val});
            vu.pb({1, y, val});
        }
        for (int j = v[i].size() - 1;j >= 0;j--) {
            int y = v[i][j].F - 1;
            ll val = max(get(1, y, n) - getc(i & 1, 0, y), 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(get(1, y, 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