Submission #818232

#	Time	Username	Problem	Language	Result	Execution time	Memory
818232		eltu0815	Catfish Farm (IOI22_fish)	C++17	84 / 100	1010 ms	622636 KiB

fish

#include "fish.h"
 
#include <bits/stdc++.h>
#define INF (ll)(1e16)
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
typedef long long ll;
typedef pair<int, int> pll;

struct Node { int l, r; ll val; };
struct SEG1 {
    vector<Node> seg[100005];
    void update(int str, int ed, int idx, ll val, int i, int node) {
        if(str == ed) { seg[i][node].val = val; return; }
        int mid = str + ed >> 1;
        if(idx <= mid) {
            if(seg[i][node].l == -1) {
                seg[i].push_back({-1, -1, -INF});
                seg[i][node].l = seg[i].size() - 1;
            }
            update(str, mid, idx, val, i, seg[i][node].l);
        }
        else {
            if(seg[i][node].r == -1) {
                seg[i].push_back({-1, -1, -INF});
                seg[i][node].r = seg[i].size() - 1;
            }
            update(mid + 1, ed, idx, val, i, seg[i][node].r);
        }
        seg[i][node].val = -INF;
        if(seg[i][node].l != -1) seg[i][node].val = max(seg[i][node].val, seg[i][seg[i][node].l].val);
        if(seg[i][node].r != -1) seg[i][node].val = max(seg[i][node].val, seg[i][seg[i][node].r].val);
    }
 
    ll query(int str, int ed, int left, int right, int i, int node) {
        if(node == -1) return -INF;
        if(str > right || ed < left) return -INF;
        if(left <= str && ed <= right) return seg[i][node].val; 
        int mid = str + ed >> 1;
        return max(query(str, mid, left, right, i, seg[i][node].l), query(mid + 1, ed, left, right, i, seg[i][node].r));
    }
} seg1, seg2, seg3;
 
struct SEG2 {
    vector<Node> seg[100005];
    void update(int str, int ed, int idx, ll val, int i, int node) {
        if(str == ed) { seg[i][node].val = val; return; }
        int mid = str + ed >> 1;
        if(idx <= mid) {
            if(seg[i][node].l == -1) {
                seg[i].push_back({-1, -1, 0});
                seg[i][node].l = seg[i].size() - 1;
            }
            update(str, mid, idx, val, i, seg[i][node].l);
        }
        else {
            if(seg[i][node].r == -1) {
                seg[i].push_back({-1, -1, 0});
                seg[i][node].r = seg[i].size() - 1;
            }
            update(mid + 1, ed, idx, val, i, seg[i][node].r);
        }
        seg[i][node].val = 0;
        if(seg[i][node].l != -1) seg[i][node].val += seg[i][seg[i][node].l].val;
        if(seg[i][node].r != -1) seg[i][node].val += seg[i][seg[i][node].r].val;
    }
 
    ll query(int str, int ed, int left, int right, int i, int node) {
        if(node == -1) return 0;
        if(str > right || ed < left) return 0;
        if(left <= str && ed <= right) return seg[i][node].val; 
        int mid = str + ed >> 1;
        return query(str, mid, left, right, i, seg[i][node].l) + query(mid + 1, ed, left, right, i, seg[i][node].r);
    }
} seg;
 
vector<pll> H[100005];
vector<ll> dp1[100005], dp2[100005];
 
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    for(int i = 0; i < N; ++i) H[i].push_back({N, 0});
    for(int i = 0; i < M; ++i) H[X[i]].push_back({Y[i], W[i]});
    for(int i = 0; i < N; ++i) {
        seg1.seg[i].push_back({-1, -1, -INF});
        seg2.seg[i].push_back({-1, -1, -INF});
        seg3.seg[i].push_back({-1, -1, -INF});
        seg.seg[i].push_back({-1, -1, 0});
    }
    for(int i = 0; i < N; ++i) dp1[i].resize(H[i].size(), -INF), dp2[i].resize(H[i].size());
    for(int i = 0; i < N; ++i) for(auto j : H[i]) seg.update(0, N, j.first, j.second, i, 0);
    
    auto update = [&](int i) -> void {
        for(int j = 0; j < (int)H[i].size(); ++j) {
            seg1.update(0, N, H[i][j].first, dp1[i][j] - seg.query(0, N, 0, H[i][j].first - 1, i, 0), i, 0);
            seg2.update(0, N, H[i][j].first, dp2[i][j], i, 0);
            seg3.update(0, N, H[i][j].first, dp2[i][j] + seg.query(0, N, 0, H[i][j].first - 1, i + 1, 0), i, 0);
        }
    };
    
    for(int j = 0; j < (int)H[0].size(); ++j) dp1[0][j] = dp2[0][j] = 0;
    for(int i = 1; i < N; ++i) {
        update(i - 1);  
        for(int j = 0; j < (int)H[i].size(); ++j) {
            dp1[i][j] = max(dp1[i][j], seg.query(0, N, 0, H[i][j].first - 1, i - 1, 0) + seg1.query(0, N, 0, H[i][j].first, i - 1, 0));
            if(i >= 2) dp1[i][j] = max(dp1[i][j], seg.query(0, N, 0, H[i][j].first - 1, i - 1, 0) + seg2.query(0, N, 0, H[i][j].first, i - 2, 0));
            if(i >= 2) dp1[i][j] = max(dp1[i][j], seg3.query(0, N, H[i][j].first, N, i - 2, 0));
            
            dp2[i][j] = dp1[i][j];
            dp2[i][j] = max(dp2[i][j], seg3.query(0, N, H[i][j].first, N, i - 1, 0) - seg.query(0, N, 0, H[i][j].first - 1, i, 0));
        }
    }
    
    ll ret = 0;
    for(int i = 0; i < H[N - 1].size(); ++i) ret = max(ret, dp2[N - 1][i]);
    return ret;
}

Compilation message (stderr)

fish.cpp: In member function 'void SEG1::update(int, int, int, ll, int, int)':
fish.cpp:19:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish.cpp: In member function 'll SEG1::query(int, int, int, int, int, int)':
fish.cpp:43:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish.cpp: In member function 'void SEG2::update(int, int, int, ll, int, int)':
fish.cpp:52:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish.cpp: In member function 'll SEG2::query(int, int, int, int, int, int)':
fish.cpp:76:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i = 0; i < H[N - 1].size(); ++i) ret = max(ret, dp2[N - 1][i]);
      |                    ~~^~~~~~~~~~~~~~~~~

• 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: 0 / 16