Submission #232121

#	Time	Username	Problem	Language	Result	Execution time	Memory
232121		Kubalionzzale	Safety (NOI18_safety)	C++14	0 / 100	126 ms	7928 KiB

safety

#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
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 5
• Subtask 5: 0 / 6
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29