oj.uz

Submission #939509

# Submission time Handle Problem Language Result Execution time Memory
939509 2024-03-06T12:35:02 Z boris_mihov Treatment Project (JOI20_treatment) C++17
5 / 100
 2984 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 * 40];
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;

        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 < 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);
        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 2984 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 36 ms 96500 KB Output is correct
2 Correct 33 ms 96092 KB Output is correct
3 Correct 33 ms 96112 KB Output is correct
4 Correct 32 ms 96084 KB Output is correct
5 Correct 32 ms 96092 KB Output is correct
6 Correct 32 ms 96092 KB Output is correct
7 Correct 32 ms 96128 KB Output is correct
8 Correct 32 ms 96080 KB Output is correct
9 Correct 35 ms 96092 KB Output is correct
10 Correct 33 ms 96092 KB Output is correct
11 Correct 33 ms 96092 KB Output is correct
12 Correct 32 ms 96248 KB Output is correct
13 Correct 32 ms 96084 KB Output is correct
14 Correct 32 ms 96092 KB Output is correct
15 Correct 32 ms 96092 KB Output is correct
16 Correct 31 ms 96204 KB Output is correct
17 Correct 36 ms 96264 KB Output is correct
18 Correct 38 ms 96088 KB Output is correct
19 Correct 40 ms 96080 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 96500 KB Output is correct
2 Correct 33 ms 96092 KB Output is correct
3 Correct 33 ms 96112 KB Output is correct
4 Correct 32 ms 96084 KB Output is correct
5 Correct 32 ms 96092 KB Output is correct
6 Correct 32 ms 96092 KB Output is correct
7 Correct 32 ms 96128 KB Output is correct
8 Correct 32 ms 96080 KB Output is correct
9 Correct 35 ms 96092 KB Output is correct
10 Correct 33 ms 96092 KB Output is correct
11 Correct 33 ms 96092 KB Output is correct
12 Correct 32 ms 96248 KB Output is correct
13 Correct 32 ms 96084 KB Output is correct
14 Correct 32 ms 96092 KB Output is correct
15 Correct 32 ms 96092 KB Output is correct
16 Correct 31 ms 96204 KB Output is correct
17 Correct 36 ms 96264 KB Output is correct
18 Correct 38 ms 96088 KB Output is correct
19 Correct 40 ms 96080 KB Output is correct
20 Runtime error 132 ms 217144 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 2984 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -