oj.uz

Submission #993119

# Submission time Handle Problem Language Result Execution time Memory
993119 2024-06-05T10:28:41 Z Programmer123 Train (APIO24_train) C++17
40 / 100
 543 ms 180548 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)) * ((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;
        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]) + 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 344 KB Correct.
2 Correct 1 ms 1116 KB Correct.
3 Correct 2 ms 604 KB Correct.
4 Correct 1 ms 604 KB Correct.
5 Correct 0 ms 344 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 128 ms 17660 KB Correct.
2 Correct 176 ms 76980 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 44 ms 68508 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 136 ms 14520 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 115 ms 78156 KB Correct.
9 Correct 193 ms 78008 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 17660 KB Correct.
2 Correct 176 ms 76980 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 44 ms 68508 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 136 ms 14520 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 115 ms 78156 KB Correct.
9 Correct 193 ms 78008 KB Correct.
10 Correct 409 ms 118936 KB Correct.
11 Correct 412 ms 180548 KB Correct.
12 Correct 42 ms 68436 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 385 ms 111468 KB Correct.
15 Correct 443 ms 179352 KB Correct.
16 Correct 398 ms 112024 KB Correct.
17 Correct 334 ms 163228 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 1 ms 1116 KB Correct.
3 Correct 2 ms 604 KB Correct.
4 Correct 1 ms 604 KB Correct.
5 Correct 0 ms 344 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 128 ms 17660 KB Correct.
9 Correct 176 ms 76980 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 44 ms 68508 KB Correct.
12 Correct 0 ms 344 KB Correct.
13 Correct 136 ms 14520 KB Correct.
14 Correct 0 ms 344 KB Correct.
15 Correct 115 ms 78156 KB Correct.
16 Correct 193 ms 78008 KB Correct.
17 Correct 409 ms 118936 KB Correct.
18 Correct 412 ms 180548 KB Correct.
19 Correct 42 ms 68436 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Correct 385 ms 111468 KB Correct.
22 Correct 443 ms 179352 KB Correct.
23 Correct 398 ms 112024 KB Correct.
24 Correct 334 ms 163228 KB Correct.
25 Correct 486 ms 169628 KB Correct.
26 Correct 473 ms 169372 KB Correct.
27 Correct 543 ms 169812 KB Correct.
28 Correct 536 ms 169284 KB Correct.
29 Correct 459 ms 109464 KB Correct.
30 Correct 442 ms 103328 KB Correct.
31 Correct 423 ms 101804 KB Correct.
32 Correct 452 ms 103780 KB Correct.
33 Correct 451 ms 101528 KB Correct.
34 Incorrect 424 ms 104104 KB Wrong Answer.
35 Halted 0 ms 0 KB -