oj.uz

Submission #939505

# Submission time Handle Problem Language Result Execution time Memory
939505 2024-03-06T12:31:04 Z boris_mihov Treatment Project (JOI20_treatment) C++17
5 / 100
 3000 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;
        build(l, mid, tree[node].left, order);
        build(mid + 1, r, tree[node].right, order);
        tree[node].val = ++nodeCounter;
        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;
            update(l, mid, tree[newNode].left, tree[oldNode].left, queryPos, queryVal);
        } else
        {
            tree[newNode].right = ++cnt;
            update(mid + 1, r, tree[newNode].right, tree[oldNode].right, queryPos, queryVal);
        }

        tree[newNode].val = ++nodeCounter;
        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 Execution timed out 3001 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 142936 KB Output is correct
2 Correct 53 ms 143004 KB Output is correct
3 Correct 53 ms 142792 KB Output is correct
4 Correct 55 ms 143000 KB Output is correct
5 Correct 53 ms 142932 KB Output is correct
6 Correct 53 ms 143016 KB Output is correct
7 Correct 53 ms 142928 KB Output is correct
8 Correct 51 ms 142940 KB Output is correct
9 Correct 53 ms 142940 KB Output is correct
10 Correct 56 ms 142960 KB Output is correct
11 Correct 53 ms 142928 KB Output is correct
12 Correct 52 ms 142932 KB Output is correct
13 Correct 52 ms 142940 KB Output is correct
14 Correct 53 ms 142872 KB Output is correct
15 Correct 52 ms 142876 KB Output is correct
16 Correct 54 ms 142856 KB Output is correct
17 Correct 53 ms 142792 KB Output is correct
18 Correct 52 ms 142980 KB Output is correct
19 Correct 53 ms 142892 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 142936 KB Output is correct
2 Correct 53 ms 143004 KB Output is correct
3 Correct 53 ms 142792 KB Output is correct
4 Correct 55 ms 143000 KB Output is correct
5 Correct 53 ms 142932 KB Output is correct
6 Correct 53 ms 143016 KB Output is correct
7 Correct 53 ms 142928 KB Output is correct
8 Correct 51 ms 142940 KB Output is correct
9 Correct 53 ms 142940 KB Output is correct
10 Correct 56 ms 142960 KB Output is correct
11 Correct 53 ms 142928 KB Output is correct
12 Correct 52 ms 142932 KB Output is correct
13 Correct 52 ms 142940 KB Output is correct
14 Correct 53 ms 142872 KB Output is correct
15 Correct 52 ms 142876 KB Output is correct
16 Correct 54 ms 142856 KB Output is correct
17 Correct 53 ms 142792 KB Output is correct
18 Correct 52 ms 142980 KB Output is correct
19 Correct 53 ms 142892 KB Output is correct
20 Runtime error 187 ms 312116 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3001 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -