Submission #993601

#	Time	Username	Problem	Language	Result	Execution time	Memory
993601		Programmer123	Train (APIO24_train)	C++17	100 / 100	523 ms	179092 KiB

train

#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)) * ((long long) 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;
#ifdef SLOW
        auto best = INF;
        for (auto [p, c]: current[node]) {
            best = std::min(best, score(p, c, node));
        }
        return best;
#else
        return score(current[node][0].first, current[node][0].second, node);
#endif
    };
    auto add = [&](int node, int p, long long c) {
#ifndef SLOW
        while (((!current[node].empty()) &&
                score(p, c, node) <= score(current[node].back().first, current[node].back().second, node)) ||
               (current[node].size() > 1 &&
                (overTake(current[node].back().first, p, 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();
        }
#endif
        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]) + 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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60