oj.uz

Submission #701586

# Submission time Handle Problem Language Result Execution time Memory
701586 2023-02-21T14:18:49 Z boris_mihov Catfish Farm (IOI22_fish) C++17
18 / 100
 884 ms 193612 KB 
#include "fish.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXM = 600000 + 10;

struct Position
{
    int y;
    int idx;
    llong in;
    llong left;
    llong right;

    Position(int _y, int _idx, llong _in, llong _left, llong _right)
    {
        y = _y;
        idx = _idx;
        left = _left;
        right = _right;
        in = _in;
    }
};

int cnt;
struct SegmentTree
{
    llong tree[4*MAXM];
    SegmentTree()
    {
        std::fill(tree, tree + 4*MAXM, (llong)-1e18);
    }

    void update(int l, int r, int node, int queryIdx, llong value)
    {
        if (l == r)
        {
            tree[node] = value;
            return;
        }

        int mid = (l + r) / 2;
        if (queryIdx <= mid) update(l, mid, 2*node, queryIdx, value);
        else update(mid + 1, r, 2*node + 1, queryIdx, value);
        tree[node] = std::max(tree[2*node], tree[2*node + 1]);
    }

    llong query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        llong ans = -1e18;
        int mid = (l + r) / 2;
        if (queryL <= mid) ans = std::max(ans, query(l, mid, 2*node, queryL, queryR));
        if (mid + 1 <= queryR) ans = std::max(ans, query(mid + 1, r, 2*node + 1, queryL, queryR));
        return ans; 
    }

    void update(int pos, llong value)
    {
        update(1, cnt, 1, pos, value);
    }

    llong query(int l, int r)
    {
        return query(1, cnt, 1, l, r);
    }
};

int n, m;
llong dp[MAXM][2];
std::vector <Position> pos[MAXN];
std::vector <Position> posUncleared[MAXN];
std::vector <std::pair <int,int>> fish[MAXN];
SegmentTree LR[2], minusL[2], minusIN[2];

llong max_weights(int N, int M, std::vector <int> X, std::vector <int> Y, std::vector <int> W) 
{
    n = N; m = M;   
    for (int i = 0 ; i < m ; ++i)
    {
        fish[X[i] + 1].emplace_back(Y[i] + 1, W[i]);
    }

    for (int x = 1 ; x <= n ; ++x)
    {
        std::sort(fish[x].begin(), fish[x].end());
        for (const auto &[y, w] : fish[x])
        {
            if (x != 1)
            {
                posUncleared[x - 1].push_back({y, 0, 0LL, 0LL, 0LL});
            }

            if (x != n)
            {
                posUncleared[x + 1].push_back({y, 0, 0LL, 0LL, 0LL});
            }
        }
    }

    for (int x = 1 ; x <= n ; ++x)
    {
        std::sort(posUncleared[x].begin(), posUncleared[x].end(), [&](Position a, Position b)
        {
            return a.y < b.y;
        });
        
        for (Position p : posUncleared[x])
        {
            if (!pos[x].empty() && pos[x].back().y == p.y)
            {
                continue;
            }

            p.idx = ++cnt;
            pos[x].push_back(p);
        }

        int ptrL = 0;
        int ptrR = 0;
        int ptrIN = 0;
        llong inSum = 0;
        llong leftSum = 0;
        llong rightSum = 0;
        for (Position &p : pos[x])
        {
            while (ptrL < fish[x - 1].size() && fish[x - 1][ptrL].first <= p.y)
            {
                leftSum += fish[x - 1][ptrL].second;
                ptrL++;
            }

            while (ptrR < fish[x + 1].size() && fish[x + 1][ptrR].first <= p.y)
            {
                rightSum += fish[x + 1][ptrR].second;
                ptrR++;
            }

            while (ptrIN < fish[x].size() && fish[x][ptrIN].first <= p.y)
            {
                inSum += fish[x][ptrIN].second;
                ptrIN++;
            }

            p.in = inSum;
            p.left = leftSum;
            p.right = rightSum;
        }
    }
    
    for (int x = n ; x >= 1 ; --x)
    {
        for (int type = 0 ; type < 2 ; ++type)
        {
            for (const Position &curr : pos[x])
            {
                if (x == n)
                {
                    minusL[type].update(curr.idx, dp[curr.idx][type] - curr.left + curr.right);
                    minusIN[type].update(curr.idx, dp[curr.idx][type] - curr.in + curr.right);
                    LR[type].update(curr.idx, dp[curr.idx][type] + curr.left + curr.right);
                    continue;
                }

                int l = -1, r = pos[x + 1].size(), mid;
                while (l < r - 1)
                {
                    mid = (l + r) / 2;
                    if (pos[x + 1][mid].y < curr.y) l = mid;
                    else r = mid;
                }

                if (l >= 0)
                {
                    dp[curr.idx][type] = std::max(dp[curr.idx][type], minusIN[1].query(pos[x + 1][0].idx, pos[x + 1][l].idx));
                }

                if (r < pos[x + 1].size() && type == 0)
                {
                    dp[curr.idx][type] = std::max(dp[curr.idx][type], LR[0].query(pos[x + 1][r].idx, pos[x + 1].back().idx) - curr.in - curr.right);
                }

                if (x + 2 <= n)
                {
                    l = -1;
                    r = pos[x + 2].size();
                    while (l < r - 1)
                    {
                        mid = (l + r) / 2;
                        if (pos[x + 2][mid].y < curr.y) l = mid;
                        else r = mid;
                    }

                    if (l >= 0)
                    {
                        dp[curr.idx][type] = std::max(dp[curr.idx][type], minusL[0].query(pos[x + 2][0].idx, pos[x + 2][l].idx));
                    }

                    if (r < pos[x + 2].size())
                    {
                        dp[curr.idx][type] = std::max(dp[curr.idx][type], LR[0].query(pos[x + 2][r].idx, pos[x + 2].back().idx) - curr.right);
                    }
                }

                int firstIdx = pos[x].back().idx + 1;
                if (!pos[x + 1].empty())
                {
                    firstIdx = pos[x + 1].back().idx + 1;
                }

                if (!pos[x + 2].empty())
                {
                    firstIdx = pos[x + 2].back().idx + 1;
                }

                if (firstIdx <= cnt)
                {
                    dp[curr.idx][type] = std::max(dp[curr.idx][type], LR[0].query(firstIdx, cnt));
                }

                minusL[type].update(curr.idx, dp[curr.idx][type] - curr.left + curr.right);
                minusIN[type].update(curr.idx, dp[curr.idx][type] - curr.in + curr.right);
                LR[type].update(curr.idx, dp[curr.idx][type] + curr.left + curr.right);
            }
        }
    }

    return LR[0].query(1, cnt);
}

Compilation message

fish.cpp: In function 'llong max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:136:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             while (ptrL < fish[x - 1].size() && fish[x - 1][ptrL].first <= p.y)
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:142:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |             while (ptrR < fish[x + 1].size() && fish[x + 1][ptrR].first <= p.y)
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:148:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |             while (ptrIN < fish[x].size() && fish[x][ptrIN].first <= p.y)
      |                    ~~~~~~^~~~~~~~~~~~~~~~
fish.cpp:187:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Position>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |                 if (r < pos[x + 1].size() && type == 0)
      |                     ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:208:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Position>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |                     if (r < pos[x + 2].size())
      |                         ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 131260 KB Output is correct
2 Correct 133 ms 132432 KB Output is correct
3 Correct 47 ms 119996 KB Output is correct
4 Correct 48 ms 120012 KB Output is correct
5 Correct 757 ms 179820 KB Output is correct
6 Correct 884 ms 193612 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 119944 KB Output is correct
2 Correct 390 ms 144016 KB Output is correct
3 Correct 477 ms 148560 KB Output is correct
4 Correct 121 ms 131192 KB Output is correct
5 Correct 134 ms 132484 KB Output is correct
6 Correct 52 ms 120048 KB Output is correct
7 Correct 50 ms 120032 KB Output is correct
8 Correct 47 ms 120040 KB Output is correct
9 Correct 47 ms 120140 KB Output is correct
10 Correct 48 ms 120000 KB Output is correct
11 Correct 48 ms 120012 KB Output is correct
12 Correct 206 ms 136404 KB Output is correct
13 Correct 235 ms 138760 KB Output is correct
14 Correct 179 ms 132776 KB Output is correct
15 Correct 226 ms 133660 KB Output is correct
16 Correct 186 ms 132808 KB Output is correct
17 Correct 197 ms 133652 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 119932 KB Output is correct
2 Correct 47 ms 120060 KB Output is correct
3 Correct 125 ms 130856 KB Output is correct
4 Correct 105 ms 127420 KB Output is correct
5 Correct 190 ms 139524 KB Output is correct
6 Correct 185 ms 139596 KB Output is correct
7 Correct 188 ms 139596 KB Output is correct
8 Correct 194 ms 139628 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 120012 KB Output is correct
2 Correct 46 ms 120012 KB Output is correct
3 Correct 47 ms 120036 KB Output is correct
4 Correct 47 ms 120008 KB Output is correct
5 Correct 46 ms 119980 KB Output is correct
6 Correct 48 ms 120012 KB Output is correct
7 Correct 46 ms 119972 KB Output is correct
8 Correct 58 ms 119996 KB Output is correct
9 Correct 48 ms 120144 KB Output is correct
10 Correct 52 ms 120292 KB Output is correct
11 Incorrect 55 ms 120128 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278441359083'
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 120012 KB Output is correct
2 Correct 46 ms 120012 KB Output is correct
3 Correct 47 ms 120036 KB Output is correct
4 Correct 47 ms 120008 KB Output is correct
5 Correct 46 ms 119980 KB Output is correct
6 Correct 48 ms 120012 KB Output is correct
7 Correct 46 ms 119972 KB Output is correct
8 Correct 58 ms 119996 KB Output is correct
9 Correct 48 ms 120144 KB Output is correct
10 Correct 52 ms 120292 KB Output is correct
11 Incorrect 55 ms 120128 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278441359083'
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 120012 KB Output is correct
2 Correct 46 ms 120012 KB Output is correct
3 Correct 47 ms 120036 KB Output is correct
4 Correct 47 ms 120008 KB Output is correct
5 Correct 46 ms 119980 KB Output is correct
6 Correct 48 ms 120012 KB Output is correct
7 Correct 46 ms 119972 KB Output is correct
8 Correct 58 ms 119996 KB Output is correct
9 Correct 48 ms 120144 KB Output is correct
10 Correct 52 ms 120292 KB Output is correct
11 Incorrect 55 ms 120128 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278441359083'
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 119932 KB Output is correct
2 Correct 47 ms 120060 KB Output is correct
3 Correct 125 ms 130856 KB Output is correct
4 Correct 105 ms 127420 KB Output is correct
5 Correct 190 ms 139524 KB Output is correct
6 Correct 185 ms 139596 KB Output is correct
7 Correct 188 ms 139596 KB Output is correct
8 Correct 194 ms 139628 KB Output is correct
9 Correct 309 ms 144368 KB Output is correct
10 Correct 213 ms 136396 KB Output is correct
11 Correct 386 ms 152940 KB Output is correct
12 Correct 47 ms 120040 KB Output is correct
13 Correct 47 ms 120008 KB Output is correct
14 Correct 52 ms 119948 KB Output is correct
15 Correct 49 ms 120008 KB Output is correct
16 Correct 48 ms 119988 KB Output is correct
17 Correct 56 ms 120112 KB Output is correct
18 Correct 52 ms 119964 KB Output is correct
19 Correct 49 ms 119968 KB Output is correct
20 Correct 50 ms 119984 KB Output is correct
21 Correct 55 ms 120048 KB Output is correct
22 Incorrect 355 ms 144268 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45479946212981'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 131260 KB Output is correct
2 Correct 133 ms 132432 KB Output is correct
3 Correct 47 ms 119996 KB Output is correct
4 Correct 48 ms 120012 KB Output is correct
5 Correct 757 ms 179820 KB Output is correct
6 Correct 884 ms 193612 KB Output is correct
7 Correct 47 ms 119944 KB Output is correct
8 Correct 390 ms 144016 KB Output is correct
9 Correct 477 ms 148560 KB Output is correct
10 Correct 121 ms 131192 KB Output is correct
11 Correct 134 ms 132484 KB Output is correct
12 Correct 52 ms 120048 KB Output is correct
13 Correct 50 ms 120032 KB Output is correct
14 Correct 47 ms 120040 KB Output is correct
15 Correct 47 ms 120140 KB Output is correct
16 Correct 48 ms 120000 KB Output is correct
17 Correct 48 ms 120012 KB Output is correct
18 Correct 206 ms 136404 KB Output is correct
19 Correct 235 ms 138760 KB Output is correct
20 Correct 179 ms 132776 KB Output is correct
21 Correct 226 ms 133660 KB Output is correct
22 Correct 186 ms 132808 KB Output is correct
23 Correct 197 ms 133652 KB Output is correct
24 Correct 47 ms 119932 KB Output is correct
25 Correct 47 ms 120060 KB Output is correct
26 Correct 125 ms 130856 KB Output is correct
27 Correct 105 ms 127420 KB Output is correct
28 Correct 190 ms 139524 KB Output is correct
29 Correct 185 ms 139596 KB Output is correct
30 Correct 188 ms 139596 KB Output is correct
31 Correct 194 ms 139628 KB Output is correct
32 Correct 58 ms 120012 KB Output is correct
33 Correct 46 ms 120012 KB Output is correct
34 Correct 47 ms 120036 KB Output is correct
35 Correct 47 ms 120008 KB Output is correct
36 Correct 46 ms 119980 KB Output is correct
37 Correct 48 ms 120012 KB Output is correct
38 Correct 46 ms 119972 KB Output is correct
39 Correct 58 ms 119996 KB Output is correct
40 Correct 48 ms 120144 KB Output is correct
41 Correct 52 ms 120292 KB Output is correct
42 Incorrect 55 ms 120128 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278441359083'
43 Halted 0 ms 0 KB -