oj.uz

Submission #939506

# Submission time Handle Problem Language Result Execution time Memory
939506 2024-03-06T12:32:02 Z boris_mihov Treatment Project (JOI20_treatment) C++17
5 / 100
 2810 ms 524288 KB 
#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 * 60];
int nodeCounter;

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

    Node tree[MAXN * 30];
    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 < 30 * MAXN);
        build(l, mid, tree[node].left, order);
        build(mid + 1, r, tree[node].right, order);
        tree[node].val = ++nodeCounter;
        assert(nodeCounter < 60 * MAXN);
        tree[node].edgeValue = 0;

        g[tree[node].val].push_back({tree[tree[node].left].val, tree[tree[node].left].edgeValue});
        g[tree[node].val].push_back({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 < 30 * MAXN);
            update(l, mid, tree[newNode].left, tree[oldNode].left, queryPos, queryVal);
        } else
        {
            tree[newNode].right = ++cnt;
            assert(cnt < 30 * MAXN);
            update(mid + 1, r, tree[newNode].right, tree[oldNode].right, queryPos, queryVal);
        }

        tree[newNode].val = ++nodeCounter;
        assert(nodeCounter < 60 * MAXN);
        g[tree[newNode].val].resize(2);
        g[tree[newNode].val][0] = {tree[tree[newNode].left].val, tree[tree[newNode].left].edgeValue};
        g[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[MAXN];
llong dist[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;
    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 (a[node].r == m)
        {
            ans = dist[node];
            break;
        }

        if (vis[node])
        {
            continue;
        }

        vis[node] = true;
        for (const auto &[u, w] : g[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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 2810 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 142988 KB Output is correct
2 Correct 53 ms 142932 KB Output is correct
3 Correct 53 ms 142928 KB Output is correct
4 Correct 52 ms 142932 KB Output is correct
5 Correct 53 ms 142928 KB Output is correct
6 Correct 52 ms 142860 KB Output is correct
7 Correct 60 ms 143216 KB Output is correct
8 Correct 52 ms 142916 KB Output is correct
9 Correct 59 ms 142932 KB Output is correct
10 Correct 54 ms 142940 KB Output is correct
11 Correct 53 ms 142928 KB Output is correct
12 Correct 54 ms 142768 KB Output is correct
13 Correct 54 ms 143008 KB Output is correct
14 Correct 51 ms 142756 KB Output is correct
15 Correct 52 ms 142932 KB Output is correct
16 Correct 53 ms 142932 KB Output is correct
17 Correct 52 ms 142940 KB Output is correct
18 Correct 52 ms 143004 KB Output is correct
19 Correct 53 ms 142932 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 142988 KB Output is correct
2 Correct 53 ms 142932 KB Output is correct
3 Correct 53 ms 142928 KB Output is correct
4 Correct 52 ms 142932 KB Output is correct
5 Correct 53 ms 142928 KB Output is correct
6 Correct 52 ms 142860 KB Output is correct
7 Correct 60 ms 143216 KB Output is correct
8 Correct 52 ms 142916 KB Output is correct
9 Correct 59 ms 142932 KB Output is correct
10 Correct 54 ms 142940 KB Output is correct
11 Correct 53 ms 142928 KB Output is correct
12 Correct 54 ms 142768 KB Output is correct
13 Correct 54 ms 143008 KB Output is correct
14 Correct 51 ms 142756 KB Output is correct
15 Correct 52 ms 142932 KB Output is correct
16 Correct 53 ms 142932 KB Output is correct
17 Correct 52 ms 142940 KB Output is correct
18 Correct 52 ms 143004 KB Output is correct
19 Correct 53 ms 142932 KB Output is correct
20 Runtime error 187 ms 311960 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 2810 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -