Submission #992821

#	Time	Username	Problem	Language	Result	Execution time	Memory
992821		Programmer123	Train (APIO24_train)	C++17	5 / 100	120 ms	14776 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];
            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 - 1] : 0, k);
            }
        }
    };
}

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);
    }
};

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);
    std::vector<std::pair<int, int>> 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 getBest = [&](int node) {
        long long ans = LONG_LONG_MAX;
        for (auto [p, c]: current[node]) {
            ans = std::min(ans, c + ((long long) tree.query(p)) * mealCost[node]);
        }
        return ans;
    };
    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] != LONG_LONG_MAX) {
                edgeTime[idx] += cost[idx];
            }
        } else {
            if (edgeTime[idx] != LONG_LONG_MAX)
                current[end[idx]].emplace_back(time, edgeTime[idx]);
        }
    }
    auto res = getBest(nodes - 1);
    if (res == LONG_LONG_MAX) return -1;
    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) {
      |                         ~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60