oj.uz

Submission #702588

# Submission time Handle Problem Language Result Execution time Memory
702588 2023-02-24T13:36:47 Z boris_mihov Catfish Farm (IOI22_fish) C++17
67 / 100
 1000 ms 130100 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[1 << 21];
    SegmentTree()
    {
        std::fill(tree, tree + (1 << 21), (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, node << 1, queryIdx, value);
        else update(mid + 1, r, (node << 1) | 1, queryIdx, value);
        tree[node] = std::max(tree[node << 1], tree[(node << 1) | 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, node << 1, queryL, queryR));
        if (mid + 1 <= queryR) ans = std::max(ans, query(mid + 1, r, (node << 1) | 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, minusL, minusIN;
 
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;
            }
 
            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 = 1 ; x <= n ; ++x)
    {
        for (Position &p : pos[x])
        {
            p.idx = ++cnt;
        }
    }

    for (int x = n ; x >= 1 ; --x)
    {
        for (int type = 0 ; type < 2 ; ++type)
        {
            for (const Position &curr : pos[x])
            {
                if (x == n) 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.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.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.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.query(pos[x + 2][r].idx, pos[x + 2].back().idx) - curr.right);
                    }
                }
 
                int firstIdx = pos[x].back().idx + 1;
                if (x + 1 <= n && !pos[x + 1].empty())
                {
                    firstIdx = pos[x + 1].back().idx + 1;
                }
 
                if (x + 2 <= n && !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.query(firstIdx, cnt));
                }
            }

            for (const Position &curr : pos[x])
            {
                minusIN.update(curr.idx, dp[curr.idx][1] - curr.in + curr.right);
                LR.update(curr.idx, dp[curr.idx][0] + curr.left + curr.right);
                minusL.update(curr.idx, dp[curr.idx][0] + curr.right);
            }
        }
    }
 
    return LR.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:135: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]
  135 |             while (ptrL < fish[x - 1].size() && fish[x - 1][ptrL].first <= p.y)
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:141: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]
  141 |             while (ptrR < fish[x + 1].size() && fish[x + 1][ptrR].first <= p.y)
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:147: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]
  147 |             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 93 ms 67780 KB Output is correct
2 Correct 109 ms 69016 KB Output is correct
3 Correct 24 ms 56524 KB Output is correct
4 Correct 25 ms 56588 KB Output is correct
5 Correct 753 ms 116544 KB Output is correct
6 Correct 882 ms 130100 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 56528 KB Output is correct
2 Correct 364 ms 80572 KB Output is correct
3 Correct 447 ms 84940 KB Output is correct
4 Correct 92 ms 67772 KB Output is correct
5 Correct 115 ms 69012 KB Output is correct
6 Correct 24 ms 56532 KB Output is correct
7 Correct 25 ms 56584 KB Output is correct
8 Correct 25 ms 56524 KB Output is correct
9 Correct 24 ms 56552 KB Output is correct
10 Correct 25 ms 56580 KB Output is correct
11 Correct 26 ms 56524 KB Output is correct
12 Correct 179 ms 72944 KB Output is correct
13 Correct 228 ms 75228 KB Output is correct
14 Correct 165 ms 69464 KB Output is correct
15 Correct 208 ms 70176 KB Output is correct
16 Correct 157 ms 69308 KB Output is correct
17 Correct 174 ms 70156 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 56584 KB Output is correct
2 Correct 25 ms 56564 KB Output is correct
3 Correct 103 ms 67384 KB Output is correct
4 Correct 78 ms 63984 KB Output is correct
5 Correct 171 ms 76172 KB Output is correct
6 Correct 161 ms 76088 KB Output is correct
7 Correct 171 ms 76088 KB Output is correct
8 Correct 166 ms 76116 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56532 KB Output is correct
2 Correct 22 ms 56532 KB Output is correct
3 Correct 24 ms 56592 KB Output is correct
4 Correct 24 ms 56572 KB Output is correct
5 Correct 22 ms 56564 KB Output is correct
6 Correct 24 ms 56504 KB Output is correct
7 Correct 26 ms 56528 KB Output is correct
8 Correct 25 ms 56532 KB Output is correct
9 Correct 24 ms 56660 KB Output is correct
10 Correct 27 ms 56936 KB Output is correct
11 Correct 26 ms 56744 KB Output is correct
12 Correct 27 ms 56860 KB Output is correct
13 Correct 24 ms 56564 KB Output is correct
14 Correct 26 ms 56704 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56532 KB Output is correct
2 Correct 22 ms 56532 KB Output is correct
3 Correct 24 ms 56592 KB Output is correct
4 Correct 24 ms 56572 KB Output is correct
5 Correct 22 ms 56564 KB Output is correct
6 Correct 24 ms 56504 KB Output is correct
7 Correct 26 ms 56528 KB Output is correct
8 Correct 25 ms 56532 KB Output is correct
9 Correct 24 ms 56660 KB Output is correct
10 Correct 27 ms 56936 KB Output is correct
11 Correct 26 ms 56744 KB Output is correct
12 Correct 27 ms 56860 KB Output is correct
13 Correct 24 ms 56564 KB Output is correct
14 Correct 26 ms 56704 KB Output is correct
15 Correct 25 ms 56660 KB Output is correct
16 Correct 30 ms 56968 KB Output is correct
17 Correct 133 ms 64572 KB Output is correct
18 Correct 130 ms 65044 KB Output is correct
19 Correct 125 ms 65748 KB Output is correct
20 Correct 114 ms 65452 KB Output is correct
21 Correct 114 ms 65484 KB Output is correct
22 Correct 204 ms 72144 KB Output is correct
23 Correct 54 ms 58576 KB Output is correct
24 Correct 118 ms 63136 KB Output is correct
25 Correct 27 ms 56868 KB Output is correct
26 Correct 49 ms 58372 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56532 KB Output is correct
2 Correct 22 ms 56532 KB Output is correct
3 Correct 24 ms 56592 KB Output is correct
4 Correct 24 ms 56572 KB Output is correct
5 Correct 22 ms 56564 KB Output is correct
6 Correct 24 ms 56504 KB Output is correct
7 Correct 26 ms 56528 KB Output is correct
8 Correct 25 ms 56532 KB Output is correct
9 Correct 24 ms 56660 KB Output is correct
10 Correct 27 ms 56936 KB Output is correct
11 Correct 26 ms 56744 KB Output is correct
12 Correct 27 ms 56860 KB Output is correct
13 Correct 24 ms 56564 KB Output is correct
14 Correct 26 ms 56704 KB Output is correct
15 Correct 25 ms 56660 KB Output is correct
16 Correct 30 ms 56968 KB Output is correct
17 Correct 133 ms 64572 KB Output is correct
18 Correct 130 ms 65044 KB Output is correct
19 Correct 125 ms 65748 KB Output is correct
20 Correct 114 ms 65452 KB Output is correct
21 Correct 114 ms 65484 KB Output is correct
22 Correct 204 ms 72144 KB Output is correct
23 Correct 54 ms 58576 KB Output is correct
24 Correct 118 ms 63136 KB Output is correct
25 Correct 27 ms 56868 KB Output is correct
26 Correct 49 ms 58372 KB Output is correct
27 Correct 33 ms 57300 KB Output is correct
28 Correct 568 ms 93768 KB Output is correct
29 Correct 879 ms 111452 KB Output is correct
30 Execution timed out 1087 ms 123980 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 56584 KB Output is correct
2 Correct 25 ms 56564 KB Output is correct
3 Correct 103 ms 67384 KB Output is correct
4 Correct 78 ms 63984 KB Output is correct
5 Correct 171 ms 76172 KB Output is correct
6 Correct 161 ms 76088 KB Output is correct
7 Correct 171 ms 76088 KB Output is correct
8 Correct 166 ms 76116 KB Output is correct
9 Correct 287 ms 80772 KB Output is correct
10 Correct 184 ms 73020 KB Output is correct
11 Correct 356 ms 89424 KB Output is correct
12 Correct 24 ms 56532 KB Output is correct
13 Correct 25 ms 56524 KB Output is correct
14 Correct 24 ms 56580 KB Output is correct
15 Correct 24 ms 56532 KB Output is correct
16 Correct 24 ms 56660 KB Output is correct
17 Correct 24 ms 56604 KB Output is correct
18 Correct 25 ms 56532 KB Output is correct
19 Correct 24 ms 56568 KB Output is correct
20 Correct 25 ms 56504 KB Output is correct
21 Correct 24 ms 56572 KB Output is correct
22 Correct 316 ms 80756 KB Output is correct
23 Correct 569 ms 97220 KB Output is correct
24 Correct 611 ms 98444 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 67780 KB Output is correct
2 Correct 109 ms 69016 KB Output is correct
3 Correct 24 ms 56524 KB Output is correct
4 Correct 25 ms 56588 KB Output is correct
5 Correct 753 ms 116544 KB Output is correct
6 Correct 882 ms 130100 KB Output is correct
7 Correct 23 ms 56528 KB Output is correct
8 Correct 364 ms 80572 KB Output is correct
9 Correct 447 ms 84940 KB Output is correct
10 Correct 92 ms 67772 KB Output is correct
11 Correct 115 ms 69012 KB Output is correct
12 Correct 24 ms 56532 KB Output is correct
13 Correct 25 ms 56584 KB Output is correct
14 Correct 25 ms 56524 KB Output is correct
15 Correct 24 ms 56552 KB Output is correct
16 Correct 25 ms 56580 KB Output is correct
17 Correct 26 ms 56524 KB Output is correct
18 Correct 179 ms 72944 KB Output is correct
19 Correct 228 ms 75228 KB Output is correct
20 Correct 165 ms 69464 KB Output is correct
21 Correct 208 ms 70176 KB Output is correct
22 Correct 157 ms 69308 KB Output is correct
23 Correct 174 ms 70156 KB Output is correct
24 Correct 24 ms 56584 KB Output is correct
25 Correct 25 ms 56564 KB Output is correct
26 Correct 103 ms 67384 KB Output is correct
27 Correct 78 ms 63984 KB Output is correct
28 Correct 171 ms 76172 KB Output is correct
29 Correct 161 ms 76088 KB Output is correct
30 Correct 171 ms 76088 KB Output is correct
31 Correct 166 ms 76116 KB Output is correct
32 Correct 25 ms 56532 KB Output is correct
33 Correct 22 ms 56532 KB Output is correct
34 Correct 24 ms 56592 KB Output is correct
35 Correct 24 ms 56572 KB Output is correct
36 Correct 22 ms 56564 KB Output is correct
37 Correct 24 ms 56504 KB Output is correct
38 Correct 26 ms 56528 KB Output is correct
39 Correct 25 ms 56532 KB Output is correct
40 Correct 24 ms 56660 KB Output is correct
41 Correct 27 ms 56936 KB Output is correct
42 Correct 26 ms 56744 KB Output is correct
43 Correct 27 ms 56860 KB Output is correct
44 Correct 24 ms 56564 KB Output is correct
45 Correct 26 ms 56704 KB Output is correct
46 Correct 25 ms 56660 KB Output is correct
47 Correct 30 ms 56968 KB Output is correct
48 Correct 133 ms 64572 KB Output is correct
49 Correct 130 ms 65044 KB Output is correct
50 Correct 125 ms 65748 KB Output is correct
51 Correct 114 ms 65452 KB Output is correct
52 Correct 114 ms 65484 KB Output is correct
53 Correct 204 ms 72144 KB Output is correct
54 Correct 54 ms 58576 KB Output is correct
55 Correct 118 ms 63136 KB Output is correct
56 Correct 27 ms 56868 KB Output is correct
57 Correct 49 ms 58372 KB Output is correct
58 Correct 33 ms 57300 KB Output is correct
59 Correct 568 ms 93768 KB Output is correct
60 Correct 879 ms 111452 KB Output is correct
61 Execution timed out 1087 ms 123980 KB Time limit exceeded
62 Halted 0 ms 0 KB -