Submission #939524

#	Time	Username	Problem	Language	Result	Execution time	Memory
939524		boris_mihov	Treatment Project (JOI20_treatment)	C++17	100 / 100	929 ms	294860 KiB

treatment

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
 
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 vis[40 * MAXN];
llong dist[40 * MAXN];
PersistentSegmentTree treePlus;
PersistentSegmentTree treeMinus;
std::priority_queue <std::pair <llong,int>> pq;
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;
            pq.push({-dist[i], i});
        }
    }
 
    while (pq.size())
    {
        auto [currDist, node] = pq.top();
        pq.pop();
 
        if (node <= n && a[node].r == m)
        {
            ans = dist[node];
            break;
        }
 
        if (vis[node])
        {
            continue;
        }
 
        vis[node] = true;
        if (node <= n)
        {
            for (const auto &[u, w] : g[node])
            {
                if (dist[u] > dist[node] + w)
                {
                    dist[u] = dist[node] + w;
                    pq.push({-dist[u], u});
                }
            }
        } else
        {
            for (const auto &[u, w] : gTree[node])
            {
                if (dist[u] > dist[node] + w)
                {
                    dist[u] = dist[node] + w;
                    pq.push({-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