oj.uz

Submission #232121

# Submission time Handle Problem Language Result Execution time Memory
232121 2020-05-16T06:07:58 Z Kubalionzzale Safety (NOI18_safety) C++14
0 / 100
 126 ms 7928 KB 
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using ll = long long int;

ll h;

struct LeftNode
{
    ll position, time;

    LeftNode(ll position, ll time) {this->position = position; this->time = time;}

    bool operator>(const LeftNode& other) const
    {
        ll maxtime = std::max(time, other.time);
        ll mypos = position - (maxtime - time) * h;
        ll otherpos = other.position - (maxtime - other.time) * h;

        return mypos > otherpos;
    }

    bool operator<(const LeftNode& other) const
    {
        ll maxtime = std::max(time, other.time);
        ll mypos = position - (maxtime - time) * h;
        ll otherpos = other.position - (maxtime - other.time) * h;

        return mypos < otherpos;
    }

    ll curtimepos(ll curtime)
    {
        return position - (curtime - time) * h;
    }
};

struct RightNode
{
    ll position, time;

    RightNode(ll position, ll time) {this->position = position; this->time = time;}

    bool operator<(const RightNode& other) const
    {
        ll maxtime = std::max(time, other.time);
        ll mypos = position + (maxtime - time) * h;
        ll otherpos = other.position + (maxtime - other.time) * h;

        return mypos < otherpos;
    }

    bool operator>(const RightNode& other) const
    {
        ll maxtime = std::max(time, other.time);
        ll mypos = position + (maxtime - time) * h;
        ll otherpos = other.position + (maxtime - other.time) * h;

        return mypos > otherpos;
    }

    ll curtimepos(ll curtime)
    {
        return position + (curtime-time) * h;
    }
};

bool smaller(ll x, LeftNode ln, ll time)
{
    ll nodepos = ln.curtimepos(time);
    return x < nodepos;
}

bool bigger(ll x, RightNode rn, ll time)
{
    ll nodepos = rn.curtimepos(time);
    return x > nodepos;
}

int main()
{
    std::priority_queue<LeftNode> leftprioq;

    std::priority_queue<RightNode,
                        std::vector<RightNode>,
                        std::greater<RightNode> > rightprioq;

    ll n, x, ans = 0;
    std::cin >> n >> h;

    std::cin >> x;
    leftprioq.push(LeftNode(x, 0));
    rightprioq.push(RightNode(x, 0));

    for (int i = 1; i < n; ++i)
    {
        std::cin >> x;
        LeftNode leftelem = leftprioq.top();
        RightNode rightelem = rightprioq.top();

       // std::cout << "i: " << i << "\n";
     //   std::cout << "borders: " << leftelem.curtimepos(i) << " " << rightelem.curtimepos(i) << "\n";
        if (smaller(x, leftelem, i))
        {
            ll leftnodepos = leftelem.curtimepos(i);
            leftprioq.pop();

            leftprioq.push(LeftNode(x, i));
            leftprioq.push(LeftNode(x, i));

            LeftNode nextleftnode = leftprioq.top();
            ll nextleftpos = nextleftnode.curtimepos(i);
            ans += leftnodepos - nextleftpos;

        //    std::cout << "left: " << nextleftpos << " " << leftnodepos << "\n";

            rightprioq.push(RightNode(leftnodepos, i));
        }
        else if (bigger(x, rightelem, i))
        {
            ll rightnodepos = rightelem.curtimepos(i);
            rightprioq.pop();

            rightprioq.push(RightNode(x, i));
            rightprioq.push(RightNode(x, i));

            RightNode nextrightnode = rightprioq.top();
            ll nextrightpos = nextrightnode.curtimepos(i);

            ans += nextrightpos - rightnodepos;
       //     std::cout << "right: " << rightnodepos << " " << nextrightpos << "\n";

            leftprioq.push(LeftNode(rightnodepos, i));
        }
        else
        {
            leftprioq.push(LeftNode(x, i));
            rightprioq.push(RightNode(x, i));
        }
    }

    std::cout << ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 7928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -