oj.uz

Submission #993111

# Submission time Handle Problem Language Result Execution time Memory
993111 2024-06-05T10:18:05 Z Programmer123 Train (APIO24_train) C++17
40 / 100
 578 ms 179868 KB 
#include "train.h"
#include <bits/stdc++.h>

namespace Kth {
    struct Wavelet {
        int min, max;
        std::vector<int> pfx;
        Wavelet *left, *right;

        Wavelet(int l, int r, std::vector<int> &stuff) : min(l), max(r) {
            if (stuff.empty()) return;
            if (max == min + 1) {
                left = right = nullptr;
                return;
            }
            int mid = (min + max) / 2;
            int s = 0;
            std::vector<int> L, R;
            for (auto x: stuff) {
                if (x < mid) {
                    s++;
                    L.push_back(x);
                } else {
                    R.push_back(x);
                }
                pfx.push_back(s);
            }
            stuff.clear();
            left = new Wavelet(min, mid, L);
            right = new Wavelet(mid, max, R);
        }

        int query(int l, int r, int k) {//Return value of kth (0-indexed) largest in [l,r]
            if (max == min + 1) return min;
            int numInRange = pfx[r];
            if (l) numInRange -= pfx[l - 1];
            if (numInRange > k) {
                return left->query(l ? pfx[l - 1] : 0, r ? pfx[r] - 1 : 0, k);
            } else {
                return right->query(l ? l - pfx[l - 1] : 0, r ? r - pfx[r] : 0, k - numInRange);
            }
        }
    };
}

struct Compressor {
    std::vector<int> stuff;
    std::map<int, int> res;

    void run() {
        std::sort(stuff.begin(), stuff.end());
        stuff.erase(std::unique(stuff.begin(), stuff.end()), stuff.end());
        for (int i = 0; i < stuff.size(); ++i) {
            res[stuff[i]] = i;
        }
        stuff.clear();
    }

    void operator+=(int x) {
        stuff.push_back(x);
    }

    int operator[](int x) {
        return res[x];
    }
};

struct node {
    int min, max;
    node *left, *right;
    int value;

    node(int l, int r) {
        min = l;
        max = r;
        left = right = nullptr;
        value = 0;
    }

    void add(int l, int r) {
        l = std::max(l, min);
        r = std::min(r, max);
        if (l >= max || r <= min) return;
        if (l == min && r == max) {
            value++;
            return;
        }
        if (!left) {
            left = new node(min, (min + max) / 2);
            right = new node((min + max) / 2, max);
        }
        left->add(l, r);
        right->add(l, r);
    }

    int query(int x) const {
        if (x < min || x >= max) return 0;
        return value + (left ? (left->query(x) + right->query(x)) : 0);
    }
};

struct countnode {
    int min, max;
    countnode *left, *right;
    int value;

    countnode(int l, int r) {
        min = l;
        max = r;
        left = right = nullptr;
        value = 0;
    }

    void add(int x) {
        if (x < min || x >= max) return;
        value++;
        if (max == min + 1) return;
        if (!left) {
            left = new countnode(min, (min + max) / 2);
            right = new countnode((min + max) / 2, max);
        }
        left->add(x);
        right->add(x);
    }

    int query(int l, int r) const {
        l = std::max(l, min);
        r = std::min(r, max);
        if (l >= max || r <= min) return 0;
        if (l == min && r == max) return value;
        if (!left) return 0;
        return left->query(l, r) + right->query(l, r);
    }
};

long long
solve(int nodes, int edges, int meals, std::vector<int> mealCost, std::vector<int> start, std::vector<int> end,
      std::vector<int> startTime, std::vector<int> endTime, std::vector<int> cost, std::vector<int> mealStart,
      std::vector<int> mealEnd) {
    {
        Compressor c;
        c += -1;
        for (int i = 0; i < edges; ++i) {
            c += startTime[i];
            c += endTime[i];
        }
        for (int i = 0; i < meals; ++i) {
            c += mealStart[i];
            c += mealEnd[i];
        }
        c.run();
        for (int i = 0; i < edges; ++i) {
            startTime[i] = c[startTime[i]];
            endTime[i] = c[endTime[i]];
        }
        for (int i = 0; i < meals; ++i) {
            mealStart[i] = c[mealStart[i]];
            mealEnd[i] = c[mealEnd[i]];
        }
    }
    //All times are now in [0, 400000]
    node tree(0, 800001);
    countnode countTree(0, 800001);
    for (int i = 0; i < meals; ++i) {
        countTree.add(mealStart[i]);
    }
    std::vector<std::pair<int, int>> stuff;
    for (int i = 0; i < meals; ++i) {
        stuff.emplace_back(mealStart[i], mealEnd[i]);
    }
    std::sort(stuff.begin(), stuff.end());
    std::vector<int> Stuff;
    for (auto [a, b]: stuff) {
        Stuff.push_back(b);
    }
    Kth::Wavelet kth(0, 800001, Stuff);
    std::deque<std::pair<int, long long>> current[nodes];//{pos, cost}
    current[0].emplace_back(0, 0);
    struct event {
        int time;
        int idx;
        bool departure;
        bool meal;
    };
    std::vector<event> events;
    for (int i = 0; i < edges; ++i) {
        events.push_back({startTime[i], i, true, false});
        events.push_back({endTime[i], i, false, false});
    }
    for (int i = 0; i < meals; ++i) {
        events.push_back({mealEnd[i], i, false, true});
    }
    std::sort(events.begin(), events.end(), [&](event a, event b) {
        if (a.time == b.time && a.meal == b.meal) return a.departure < b.departure;
        if (a.time == b.time) return a.meal < b.meal;
        return a.time < b.time;
    });
    auto overTake = [&](int p1, int p2, long long diff, int cost) {//Diff = cost[p2]-cost[p1]
        if (diff <= 0) return 0;
        if (p1 == p2) return INT_MAX;
        if (cost == 0) return INT_MAX;
        long long needed = (diff + cost - 1) / cost;//As soon as *at least* needed, go
        if (countTree.query(p1 + 1, p2 + 1) < needed) return INT_MAX;
        int lidx = countTree.query(0, p1 + 1);
        int ridx = countTree.query(0, p2 + 1) - 1;
        assert(stuff[lidx].first > p1);
        assert(stuff[ridx].first <= p2);
        if (lidx) assert(stuff[lidx - 1].first <= p1);
        if (ridx < stuff.size() - 1) assert(stuff[ridx + 1].first > p2);
        int res = kth.query(lidx, ridx, (int) needed - 1);
        return res;
    };
    auto score = [&](int p, long long c, int node) {
        return c + ((long long) tree.query(p)) * mealCost[node];
    };
    const long long INF = LONG_LONG_MAX / 2;
    auto getBest = [&](int node) {
        while (current[node].size() > 1 && score(current[node][0].first, current[node][0].second, node) >=
                                           score(current[node][1].first, current[node][1].second, node)) {
            current[node].pop_front();
        }
        if (current[node].empty()) return INF;
        return score(current[node][0].first, current[node][0].second, node);
    };
    auto add = [&](int node, int p, long long c) {
        while (((!current[node].empty()) &&
                score(p, c, node) <= score(current[node].back().first, current[node].back().second, node)) ||
               (current[node].size() > 1 &&
                overTake(p, current[node].back().first, c - current[node].back().second, mealCost[node]) <=
                overTake(current[node][current[node].size() - 2].first, current[node].back().first,
                         current[node].back().second - current[node][current[node].size() - 2].second,
                         mealCost[node]))) {
            current[node].pop_back();
        }
        current[node].emplace_back(p, c);
    };
    long long edgeTime[edges];
    for (auto [time, idx, depart, meal]: events) {
        if (meal) {
            tree.add(0, mealStart[idx]);
        } else if (depart) {
            edgeTime[idx] = getBest(start[idx]);
            if (edgeTime[idx] != INF) {
                edgeTime[idx] += cost[idx];
            }
        } else {
            if (edgeTime[idx] != INF)
                add(end[idx], time, edgeTime[idx]);
//                current[end[idx]].emplace_back(time, edgeTime[idx]);
        }
    }
    auto res = getBest(nodes - 1);
    if (res == INF) return -1ll;
    return res;
}

Compilation message

train.cpp: In member function 'void Compressor::run()':
train.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int i = 0; i < stuff.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~
train.cpp: In lambda function:
train.cpp:209:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |         if (ridx < stuff.size() - 1) assert(stuff[ridx + 1].first > p2);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct.
2 Correct 1 ms 1116 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 1 ms 604 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 17636 KB Correct.
2 Correct 178 ms 76984 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 44 ms 68416 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 133 ms 14596 KB Correct.
7 Correct 1 ms 344 KB Correct.
8 Correct 121 ms 76904 KB Correct.
9 Correct 197 ms 78412 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 17636 KB Correct.
2 Correct 178 ms 76984 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 44 ms 68416 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 133 ms 14596 KB Correct.
7 Correct 1 ms 344 KB Correct.
8 Correct 121 ms 76904 KB Correct.
9 Correct 197 ms 78412 KB Correct.
10 Correct 429 ms 119960 KB Correct.
11 Correct 459 ms 179760 KB Correct.
12 Correct 60 ms 68436 KB Correct.
13 Correct 0 ms 344 KB Correct.
14 Correct 403 ms 111800 KB Correct.
15 Correct 487 ms 179868 KB Correct.
16 Correct 396 ms 112824 KB Correct.
17 Correct 347 ms 164472 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct.
2 Correct 1 ms 1116 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 1 ms 604 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 127 ms 17636 KB Correct.
9 Correct 178 ms 76984 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 44 ms 68416 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 133 ms 14596 KB Correct.
14 Correct 1 ms 344 KB Correct.
15 Correct 121 ms 76904 KB Correct.
16 Correct 197 ms 78412 KB Correct.
17 Correct 429 ms 119960 KB Correct.
18 Correct 459 ms 179760 KB Correct.
19 Correct 60 ms 68436 KB Correct.
20 Correct 0 ms 344 KB Correct.
21 Correct 403 ms 111800 KB Correct.
22 Correct 487 ms 179868 KB Correct.
23 Correct 396 ms 112824 KB Correct.
24 Correct 347 ms 164472 KB Correct.
25 Correct 476 ms 169864 KB Correct.
26 Correct 517 ms 170892 KB Correct.
27 Correct 578 ms 169624 KB Correct.
28 Correct 534 ms 169780 KB Correct.
29 Correct 479 ms 108768 KB Correct.
30 Correct 445 ms 102832 KB Correct.
31 Correct 436 ms 102552 KB Correct.
32 Correct 447 ms 103808 KB Correct.
33 Correct 474 ms 102068 KB Correct.
34 Incorrect 427 ms 104344 KB Wrong Answer.
35 Halted 0 ms 0 KB -