oj.uz

Submission #939507

# Submission time Handle Problem Language Result Execution time Memory
939507 2024-03-06T12:34:26 Z boris_mihov Treatment Project (JOI20_treatment) C++17
5 / 100
 2840 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();
        assert(node < 60 * MAXN);
        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 2840 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 54 ms 142932 KB Output is correct
2 Correct 51 ms 142932 KB Output is correct
3 Correct 52 ms 142940 KB Output is correct
4 Correct 54 ms 142996 KB Output is correct
5 Correct 53 ms 142932 KB Output is correct
6 Correct 60 ms 142940 KB Output is correct
7 Correct 53 ms 143016 KB Output is correct
8 Correct 52 ms 142932 KB Output is correct
9 Correct 52 ms 142924 KB Output is correct
10 Correct 53 ms 142988 KB Output is correct
11 Correct 58 ms 142940 KB Output is correct
12 Correct 54 ms 142928 KB Output is correct
13 Correct 53 ms 143048 KB Output is correct
14 Correct 53 ms 142764 KB Output is correct
15 Correct 54 ms 142932 KB Output is correct
16 Correct 54 ms 142932 KB Output is correct
17 Correct 52 ms 143008 KB Output is correct
18 Correct 53 ms 142964 KB Output is correct
19 Correct 58 ms 142928 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 142932 KB Output is correct
2 Correct 51 ms 142932 KB Output is correct
3 Correct 52 ms 142940 KB Output is correct
4 Correct 54 ms 142996 KB Output is correct
5 Correct 53 ms 142932 KB Output is correct
6 Correct 60 ms 142940 KB Output is correct
7 Correct 53 ms 143016 KB Output is correct
8 Correct 52 ms 142932 KB Output is correct
9 Correct 52 ms 142924 KB Output is correct
10 Correct 53 ms 142988 KB Output is correct
11 Correct 58 ms 142940 KB Output is correct
12 Correct 54 ms 142928 KB Output is correct
13 Correct 53 ms 143048 KB Output is correct
14 Correct 53 ms 142764 KB Output is correct
15 Correct 54 ms 142932 KB Output is correct
16 Correct 54 ms 142932 KB Output is correct
17 Correct 52 ms 143008 KB Output is correct
18 Correct 53 ms 142964 KB Output is correct
19 Correct 58 ms 142928 KB Output is correct
20 Runtime error 198 ms 311888 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 2840 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -