oj.uz

Submission #993079

# Submission time Handle Problem Language Result Execution time Memory
993079 2024-06-05T09:55:41 Z Programmer123 Train (APIO24_train) C++17
40 / 100
 576 ms 181144 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);
        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) {
      |                         ~~^~~~~~~~~~~~~~
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 2 ms 1368 KB Correct.
3 Correct 2 ms 604 KB Correct.
4 Correct 2 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 126 ms 17848 KB Correct.
2 Correct 175 ms 77648 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 42 ms 68336 KB Correct.
5 Correct 1 ms 344 KB Correct.
6 Correct 122 ms 14484 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 115 ms 76880 KB Correct.
9 Correct 217 ms 77972 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 17848 KB Correct.
2 Correct 175 ms 77648 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 42 ms 68336 KB Correct.
5 Correct 1 ms 344 KB Correct.
6 Correct 122 ms 14484 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 115 ms 76880 KB Correct.
9 Correct 217 ms 77972 KB Correct.
10 Correct 423 ms 118216 KB Correct.
11 Correct 419 ms 181144 KB Correct.
12 Correct 39 ms 68436 KB Correct.
13 Correct 0 ms 344 KB Correct.
14 Correct 385 ms 112044 KB Correct.
15 Correct 447 ms 179356 KB Correct.
16 Correct 404 ms 111260 KB Correct.
17 Correct 325 ms 164764 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 2 ms 1368 KB Correct.
3 Correct 2 ms 604 KB Correct.
4 Correct 2 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 126 ms 17848 KB Correct.
9 Correct 175 ms 77648 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 42 ms 68336 KB Correct.
12 Correct 1 ms 344 KB Correct.
13 Correct 122 ms 14484 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 115 ms 76880 KB Correct.
16 Correct 217 ms 77972 KB Correct.
17 Correct 423 ms 118216 KB Correct.
18 Correct 419 ms 181144 KB Correct.
19 Correct 39 ms 68436 KB Correct.
20 Correct 0 ms 344 KB Correct.
21 Correct 385 ms 112044 KB Correct.
22 Correct 447 ms 179356 KB Correct.
23 Correct 404 ms 111260 KB Correct.
24 Correct 325 ms 164764 KB Correct.
25 Correct 463 ms 169624 KB Correct.
26 Correct 493 ms 170392 KB Correct.
27 Correct 546 ms 168860 KB Correct.
28 Correct 576 ms 168604 KB Correct.
29 Correct 450 ms 107488 KB Correct.
30 Correct 446 ms 103356 KB Correct.
31 Correct 423 ms 103576 KB Correct.
32 Correct 412 ms 102812 KB Correct.
33 Correct 483 ms 102008 KB Correct.
34 Incorrect 415 ms 104600 KB Wrong Answer.
35 Halted 0 ms 0 KB -