oj.uz

Submission #993116

# Submission time Handle Problem Language Result Execution time Memory
993116 2024-06-05T10:24:20 Z Programmer123 Train (APIO24_train) C++17
40 / 100
 523 ms 180636 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, 400001);
    countnode countTree(0, 400001);
    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, 400001, 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]) ||
                 overTake(p, current[node][current[node].size() - 2].first,
                          c - current[node][current[node].size() - 2].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 2 ms 344 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 125 ms 17592 KB Correct.
2 Correct 165 ms 78008 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 39 ms 68460 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 125 ms 14504 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 141 ms 77892 KB Correct.
9 Correct 190 ms 78008 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 17592 KB Correct.
2 Correct 165 ms 78008 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 39 ms 68460 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 125 ms 14504 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 141 ms 77892 KB Correct.
9 Correct 190 ms 78008 KB Correct.
10 Correct 387 ms 119960 KB Correct.
11 Correct 398 ms 179864 KB Correct.
12 Correct 41 ms 68344 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 361 ms 111720 KB Correct.
15 Correct 450 ms 180636 KB Correct.
16 Correct 392 ms 112280 KB Correct.
17 Correct 329 ms 163124 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 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 125 ms 17592 KB Correct.
9 Correct 165 ms 78008 KB Correct.
10 Correct 1 ms 348 KB Correct.
11 Correct 39 ms 68460 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 125 ms 14504 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 141 ms 77892 KB Correct.
16 Correct 190 ms 78008 KB Correct.
17 Correct 387 ms 119960 KB Correct.
18 Correct 398 ms 179864 KB Correct.
19 Correct 41 ms 68344 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Correct 361 ms 111720 KB Correct.
22 Correct 450 ms 180636 KB Correct.
23 Correct 392 ms 112280 KB Correct.
24 Correct 329 ms 163124 KB Correct.
25 Correct 463 ms 169884 KB Correct.
26 Correct 478 ms 169780 KB Correct.
27 Correct 514 ms 169372 KB Correct.
28 Correct 523 ms 168348 KB Correct.
29 Correct 452 ms 109464 KB Correct.
30 Correct 442 ms 102044 KB Correct.
31 Correct 430 ms 102552 KB Correct.
32 Correct 428 ms 102556 KB Correct.
33 Correct 447 ms 102044 KB Correct.
34 Incorrect 428 ms 105372 KB Wrong Answer.
35 Halted 0 ms 0 KB -