Submission #939523

#	Time	Username	Problem	Language	Result	Execution time	Memory
939523		boris_mihov	Treatment Project (JOI20_treatment)	C++17	100 / 100	991 ms	301276 KiB

treatment

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 100000 + 10;
const llong INF = 1e18;

int n, m;
struct Interval
{
    int t, l, r, c;
    friend bool operator < (const Interval &a, const Interval &b)
    {
        return a.t < b.t;
    }
};

Interval a[MAXN];
std::vector <std::pair <int,llong>> g[MAXN];
std::pair <int,llong> gTree[40 * MAXN][2];
int nodeCounter;

struct PersistentSegmentTree
{
    struct Node
    {
        int val;
        int left;
        int right;
        llong edgeValue;
    };

    Node tree[MAXN * 20];
    int root;
    int cnt;

    void build(int l, int r, int node, int order[])
    {
        if (l == r)
        {
            tree[node].val = order[l];
            tree[node].edgeValue = INF;
            return;
        }

        int mid = (l + r) / 2;
        tree[node].left = ++cnt;
        tree[node].right = ++cnt;
        assert(cnt < 20 * MAXN);
        build(l, mid, tree[node].left, order);
        build(mid + 1, r, tree[node].right, order);
        tree[node].val = ++nodeCounter;
        assert(nodeCounter < 40 * MAXN);
        tree[node].edgeValue = 0;

        gTree[tree[node].val][0] = {tree[tree[node].left].val, tree[tree[node].left].edgeValue};
        gTree[tree[node].val][1] = {tree[tree[node].right].val, tree[tree[node].right].edgeValue};        
    }

    void update(int l, int r, int newNode, int oldNode, int queryPos, int queryVal)
    {
        tree[newNode] = tree[oldNode];
        if (l == r)
        {
            tree[newNode].edgeValue = queryVal;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid)
        {
            tree[newNode].left = ++cnt;
            assert(cnt < 20 * MAXN);
            update(l, mid, tree[newNode].left, tree[oldNode].left, queryPos, queryVal);
        } else
        {
            tree[newNode].right = ++cnt;
            assert(cnt < 20 * MAXN);
            update(mid + 1, r, tree[newNode].right, tree[oldNode].right, queryPos, queryVal);
        }

        tree[newNode].val = ++nodeCounter;
        assert(nodeCounter < 40 * MAXN);
        gTree[tree[newNode].val][0] = {tree[tree[newNode].left].val, tree[tree[newNode].left].edgeValue};
        gTree[tree[newNode].val][1] = {tree[tree[newNode].right].val, tree[tree[newNode].right].edgeValue};
    }

    void addEdges(int l, int r, int node, int queryL, int queryR, int from)
    {
        if (queryL <= l && r <= queryR)
        {
            g[from].push_back({tree[node].val, tree[node].edgeValue});
            return;
        }

        int mid = (l + r) / 2;
        if (queryL <= mid) addEdges(l, mid, tree[node].left, queryL, queryR, from);
        if (mid + 1 <= queryR) addEdges(mid + 1, r, tree[node].right, queryL, queryR, from);
    }

    void build(int order[])
    {
        root = 1;
        cnt = 1;
        build(1, n, root, order);
    }

    void update(int pos, int val)
    {
        int newRoot = ++cnt;
        update(1, n, newRoot, root, pos, val);
        root = newRoot;
    }

    void addEdges(int l, int r, int from)
    {
        addEdges(1, n, root, l, r, from);
    }
};

bool in[40 * MAXN];
bool vis[40 * MAXN];
llong dist[40 * MAXN];
PersistentSegmentTree treePlus;
PersistentSegmentTree treeMinus;
std::set <std::pair <llong,int>> s;
int plusOrder[MAXN];
int minusOrder[MAXN];
int inPlusOrder[MAXN];
int inMinusOrder[MAXN];

void solve()
{
    std::sort(a + 1, a + 1 + n);
    std::iota(plusOrder + 1, plusOrder + 1 + n, 1);
    std::iota(minusOrder + 1, minusOrder + 1 + n, 1);
    std::sort(plusOrder + 1, plusOrder + 1 + n, [&](int x, int y)
    {
        return a[x].l + a[x].t < a[y].l + a[y].t;
    });

    std::sort(minusOrder + 1, minusOrder + 1 + n, [&](int x, int y)
    {
        return a[x].l - a[x].t < a[y].l - a[y].t;
    });

    for (int i = 1 ; i <= n ; ++i)
    {
        inPlusOrder[plusOrder[i]] = i;
        inMinusOrder[minusOrder[i]] = i;
    }

    nodeCounter = n;
    treePlus.build(plusOrder);
    for (int i = n ; i >= 1 ; --i)
    {
        int l = 0, r = n + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (a[plusOrder[mid]].l + a[plusOrder[mid]].t <= a[i].r + a[i].t + 1) l = mid;
            else r = mid;
        }

        if (l != 0)
        {
            treePlus.addEdges(1, l, i);
        }

        treePlus.update(inPlusOrder[i], a[i].c);
    }

    treeMinus.build(minusOrder);
    for (int i = 1 ; i <= n ; ++i)
    {
        int l = 0, r = n + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (a[minusOrder[mid]].l - a[minusOrder[mid]].t <= a[i].r - a[i].t + 1) l = mid;
            else r = mid;
        }

        if (l != 0)
        {
            treeMinus.addEdges(1, l, i);
        }

        treeMinus.update(inMinusOrder[i], a[i].c);
    }

    llong ans = INF;
    assert(nodeCounter < 40 * MAXN);
    std::fill(dist + 1, dist + 1 + nodeCounter, INF);
    for (int i = 1 ; i <= n ; ++i)
    {
        if (a[i].l == 1)
        {
            dist[i] = a[i].c;
            s.insert({dist[i], i});
            in[i] = true;
        }
    }

    // if (n > 16)
    // {
    //     return;
    // }

    while (s.size())
    {
        auto [currDist, node] = (*s.begin());
        s.erase(s.begin());

        if (node <= n && a[node].r == m)
        {
            ans = dist[node];
            break;
        }

        if (vis[node])
        {
            assert(false);
        }

        vis[node] = true;
        in[node] = true;
        if (node <= n)
        {
            for (const auto &[u, w] : g[node])
            {
                if (dist[u] > dist[node] + w)
                {
                    if (in[u])
                    {
                        s.erase(s.find({dist[u], u}));
                    }

                    dist[u] = dist[node] + w;
                    s.insert({dist[u], u});
                }
            }
        } else
        {
            for (const auto &[u, w] : gTree[node])
            {
                if (dist[u] > dist[node] + w)
                {
                    if (in[u])
                    {
                        s.erase(s.find({dist[u], u}));
                    }

                    dist[u] = dist[node] + w;
                    s.insert({dist[u], u});
                }
            }
        }
    }

    if (ans == INF) std::cout << -1 << '\n';
    else std::cout << ans << '\n';
}

void input()
{
    std::cin >> m >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
    }   
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61