oj.uz

Submission #993601

# Submission time Handle Problem Language Result Execution time Memory
993601 2024-06-06T07:24:37 Z Programmer123 Train (APIO24_train) C++17
100 / 100
 523 ms 179092 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;
#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

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 17636 KB Correct.
2 Correct 170 ms 76976 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 41 ms 68416 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 129 ms 14536 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 112 ms 76904 KB Correct.
9 Correct 197 ms 76976 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 17636 KB Correct.
2 Correct 170 ms 76976 KB Correct.
3 Correct 0 ms 348 KB Correct.
4 Correct 41 ms 68416 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 129 ms 14536 KB Correct.
7 Correct 1 ms 348 KB Correct.
8 Correct 112 ms 76904 KB Correct.
9 Correct 197 ms 76976 KB Correct.
10 Correct 420 ms 117916 KB Correct.
11 Correct 398 ms 179092 KB Correct.
12 Correct 44 ms 68444 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 379 ms 111080 KB Correct.
15 Correct 414 ms 179092 KB Correct.
16 Correct 397 ms 111256 KB Correct.
17 Correct 307 ms 162708 KB Correct.

Subtask #4
60.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 348 KB Correct.
8 Correct 122 ms 17636 KB Correct.
9 Correct 170 ms 76976 KB Correct.
10 Correct 0 ms 348 KB Correct.
11 Correct 41 ms 68416 KB Correct.
12 Correct 0 ms 348 KB Correct.
13 Correct 129 ms 14536 KB Correct.
14 Correct 1 ms 348 KB Correct.
15 Correct 112 ms 76904 KB Correct.
16 Correct 197 ms 76976 KB Correct.
17 Correct 420 ms 117916 KB Correct.
18 Correct 398 ms 179092 KB Correct.
19 Correct 44 ms 68444 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Correct 379 ms 111080 KB Correct.
22 Correct 414 ms 179092 KB Correct.
23 Correct 397 ms 111256 KB Correct.
24 Correct 307 ms 162708 KB Correct.
25 Correct 457 ms 169368 KB Correct.
26 Correct 480 ms 168752 KB Correct.
27 Correct 508 ms 168332 KB Correct.
28 Correct 523 ms 168084 KB Correct.
29 Correct 444 ms 107412 KB Correct.
30 Correct 422 ms 101532 KB Correct.
31 Correct 424 ms 101564 KB Correct.
32 Correct 412 ms 102040 KB Correct.
33 Correct 462 ms 100764 KB Correct.
34 Correct 407 ms 103324 KB Correct.
35 Correct 418 ms 103432 KB Correct.
36 Correct 391 ms 103884 KB Correct.
37 Correct 438 ms 171412 KB Correct.
38 Correct 491 ms 100768 KB Correct.
39 Correct 440 ms 101268 KB Correct.
40 Correct 474 ms 169372 KB Correct.
41 Correct 291 ms 102328 KB Correct.
42 Correct 245 ms 41200 KB Correct.
43 Correct 308 ms 35488 KB Correct.
44 Correct 518 ms 168800 KB Correct.
45 Correct 493 ms 168600 KB Correct.
46 Correct 440 ms 169376 KB Correct.
47 Correct 285 ms 118168 KB Correct.
48 Correct 262 ms 108696 KB Correct.
49 Correct 257 ms 108864 KB Correct.
50 Correct 263 ms 104344 KB Correct.
51 Correct 247 ms 100244 KB Correct.
52 Correct 279 ms 103832 KB Correct.