oj.uz

답안 #701573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701573 2023-02-21T14:06:04 Z boris_mihov 메기 농장 (IOI22_fish) C++17
12 / 100
 852 ms 182928 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];
    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;   
    assert(n != 2);
    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)
    {
        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:127: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]
  127 |             while (ptrL < fish[x - 1].size() && fish[x - 1][ptrL].first <= p.y)
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:133: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]
  133 |             while (ptrR < fish[x + 1].size() && fish[x + 1][ptrR].first <= p.y)
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:139: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]
  139 |             while (ptrIN < fish[x].size() && fish[x][ptrIN].first <= p.y)
      |                    ~~~~~~^~~~~~~~~~~~~~~~
fish.cpp:178:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Position>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |                 if (r < pos[x + 1].size() && type == 0)
      |                     ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:199:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Position>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |                     if (r < pos[x + 2].size())
      |                         ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 28732 KB Output is correct
2 Correct 95 ms 30884 KB Output is correct
3 Correct 6 ms 7364 KB Output is correct
4 Correct 5 ms 7356 KB Output is correct
5 Correct 758 ms 169032 KB Output is correct
6 Correct 852 ms 182928 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 351 ms 57856 KB Output is correct
3 Correct 439 ms 88396 KB Output is correct
4 Correct 82 ms 28884 KB Output is correct
5 Correct 95 ms 30908 KB Output is correct
6 Runtime error 12 ms 14656 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7364 KB Output is correct
3 Correct 84 ms 25260 KB Output is correct
4 Correct 57 ms 21572 KB Output is correct
5 Correct 153 ms 41040 KB Output is correct
6 Correct 143 ms 40224 KB Output is correct
7 Correct 145 ms 40836 KB Output is correct
8 Correct 147 ms 40812 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7364 KB Output is correct
3 Runtime error 12 ms 14664 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7364 KB Output is correct
3 Runtime error 12 ms 14664 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7364 KB Output is correct
3 Runtime error 12 ms 14664 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7364 KB Output is correct
3 Correct 84 ms 25260 KB Output is correct
4 Correct 57 ms 21572 KB Output is correct
5 Correct 153 ms 41040 KB Output is correct
6 Correct 143 ms 40224 KB Output is correct
7 Correct 145 ms 40836 KB Output is correct
8 Correct 147 ms 40812 KB Output is correct
9 Correct 278 ms 57564 KB Output is correct
10 Correct 289 ms 54796 KB Output is correct
11 Correct 597 ms 102308 KB Output is correct
12 Runtime error 11 ms 14656 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 28732 KB Output is correct
2 Correct 95 ms 30884 KB Output is correct
3 Correct 6 ms 7364 KB Output is correct
4 Correct 5 ms 7356 KB Output is correct
5 Correct 758 ms 169032 KB Output is correct
6 Correct 852 ms 182928 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 351 ms 57856 KB Output is correct
9 Correct 439 ms 88396 KB Output is correct
10 Correct 82 ms 28884 KB Output is correct
11 Correct 95 ms 30908 KB Output is correct
12 Runtime error 12 ms 14656 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -