Submission #689668

#	Time	Username	Problem	Language	Result	Execution time	Memory
689668		lohacho	Catfish Farm (IOI22_fish)	C++17	6 / 100	540 ms	61736 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

struct Seg{
    long long n, st;

    vector<long long> tr, lazy;

    Seg(long long m):n(m + 4){
        tr.resize(n * 4 * 3, -(long long)1e18);
        lazy.resize(n * 4 * 3, -(long long)1e18);
        st = n;
        st = 0;
    }

    void update(int x, int s, int e){
        tr[x] = max(tr[x], lazy[x]);
        if(s < e){
            lazy[x * 2] = max(lazy[x * 2], lazy[x]);
            lazy[x * 2 + 1] = max(lazy[x * 2 + 1], lazy[x]);
        }
        lazy[x] = -(long long)1e18;
    }

    void push(long long x, long long s, long long e, int ps, int pe, long long val){
        if(pe < s || ps > e){
            return;
        }
        if(ps <= s && pe >= e){
            lazy[x] = max(lazy[x], val);
            update(x, s, e);
            return;
        }

        update(x, s, e);

        int m = s + e >> 1;
        push(x * 2, s, m, ps, pe, val);
        push(x * 2 + 1, m + 1, e, ps, pe, val);

        tr[x] = max(tr[x * 2], tr[x * 2 + 1]);
    }

    long long get(long long x, long long s, long long e, long long fs, long long fe){
        if(fe < s || fs > e || fs > fe) return -(long long)1e18;
        update(x, s, e);
        if(fs <= s && fe >= e){
            return tr[x];
        }

        long long m = s + e >> 1;

        return max(get(x * 2, s, m, fs, fe), get(x * 2 + 1, m + 1, e, fs, fe));
    }
};

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {

    vector<vector<long long>> a(M);
    for(long long i = 0; i < M; ++i){
        a[i] = {X[i], Y[i] + 1, W[i]};
    }

    sort(a.begin(), a.end());

    Seg dp1(N), dp2(N);

    int mx = N * 3 + 1;
    //cout << mx << endl;
    dp1.push(1, 0, mx, 0, mx, 0);

    long long ans = 0;

    for(long long i = 0, j = 0; i < N; ++i){
        long long hval = dp1.get(1, 0, mx, 0, mx);

        dp1.push(1, 0, mx, 0, mx, dp2.get(1, 0, mx, 0, mx));

        long long l = j, r = j - 1;
        while(r + 1 < M && a[r + 1][0] == i){
            ++r;
        }

        //cout << i << ' ' << l << ' ' << r << endl;

        dp1.st -= 1;
        dp2.st += 1;
        for(long long x = l; x <= r; ++x){
            dp1.push(1, 0, mx, a[x][1] + dp1.st, mx, dp1.get(1, 0, mx, a[x][1] + dp1.st, a[x][1] + dp1.st) + a[x][2]);
        }
        for(long long x = r; x >= l; --x){
            dp2.push(1, 0, mx, 0, a[x][1] + dp2.st, dp2.get(1, 0, mx, a[x][1] + dp2.st, a[x][1] + dp2.st) + a[x][2]);
        }

        dp2.push(1, 0, mx, 0, mx, hval);

        j = r + 1;

        // for(int i = 1; i <= N; ++i){
        //     cout << dp1.get(1, 0, mx, i + dp1.st, i + dp1.st) << ' ';
        // }
        // cout << endl;

        // for(int i = 1; i <= N; ++i){
        //     cout << dp2.get(1, 0, mx, i + dp1.st, i + dp1.st) << ' ';
        // }
        // cout << endl;
        ans = max(ans, dp2.get(1, 0, mx, 0, mx));
        if(i < N - 1){
            ans = max(ans, dp1.get(1, 0, mx, 0, mx));
        }
    }

    return ans;
}

Compilation message (stderr)

fish.cpp: In member function 'void Seg::push(long long int, long long int, long long int, int, int, long long int)':
fish.cpp:40:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int m = s + e >> 1;
      |                 ~~^~~
fish.cpp: In member function 'long long int Seg::get(long long int, long long int, long long int, long long int, long long int)':
fish.cpp:54:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         long long m = s + e >> 1;
      |                       ~~^~~

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