oj.uz

Submission #993054

# Submission time Handle Problem Language Result Execution time Memory
993054 2024-06-05T09:21:25 Z Programmer123 Train (APIO24_train) C++17
40 / 100
 516 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, 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;
        return kth.query(lidx, ridx, needed - 1);
    };
    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) {
      |                         ~~^~~~~~~~~~~~~~

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 600 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 17852 KB Correct.
2 Correct 168 ms 78004 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 43 ms 68420 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 126 ms 14520 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 113 ms 77124 KB Correct.
9 Correct 185 ms 78264 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 17852 KB Correct.
2 Correct 168 ms 78004 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 43 ms 68420 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 126 ms 14520 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 113 ms 77124 KB Correct.
9 Correct 185 ms 78264 KB Correct.
10 Correct 426 ms 119452 KB Correct.
11 Correct 404 ms 179864 KB Correct.
12 Correct 50 ms 68436 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 385 ms 112768 KB Correct.
15 Correct 426 ms 179868 KB Correct.
16 Correct 382 ms 112344 KB Correct.
17 Correct 313 ms 163992 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 600 KB Correct.
8 Correct 143 ms 17852 KB Correct.
9 Correct 168 ms 78004 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 43 ms 68420 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 126 ms 14520 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 113 ms 77124 KB Correct.
16 Correct 185 ms 78264 KB Correct.
17 Correct 426 ms 119452 KB Correct.
18 Correct 404 ms 179864 KB Correct.
19 Correct 50 ms 68436 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Correct 385 ms 112768 KB Correct.
22 Correct 426 ms 179868 KB Correct.
23 Correct 382 ms 112344 KB Correct.
24 Correct 313 ms 163992 KB Correct.
25 Correct 458 ms 171040 KB Correct.
26 Correct 482 ms 170392 KB Correct.
27 Correct 513 ms 169368 KB Correct.
28 Correct 516 ms 169372 KB Correct.
29 Correct 494 ms 108852 KB Correct.
30 Correct 413 ms 101784 KB Correct.
31 Correct 411 ms 101536 KB Correct.
32 Correct 402 ms 102560 KB Correct.
33 Correct 438 ms 101020 KB Correct.
34 Incorrect 407 ms 105120 KB Wrong Answer.
35 Halted 0 ms 0 KB -