Submission #986500

#	Time	Username	Problem	Language	Result	Execution time	Memory
986500		boris_mihov	Tower (JOI24_tower)	C++17	100 / 100	1214 ms	90932 KiB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 1e18;

int n, q;
int a, b;
llong d;
llong minJumps[MAXN];

std::vector <std::pair <llong,llong>> inp;
std::vector <std::pair <llong,llong>> v;

bool inInterval(llong x)
{
    int l = -1, r = v.size(), mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (v[mid].second < x) l = mid;
        else r = mid;
    }

    return r != v.size() && v[r].first <= x;
}

int getInterval(llong x)
{
    int l = -1, r = v.size(), mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (v[mid].second < x) l = mid;
        else r = mid;
    }

    return r;
}

std::map <llong, llong> dp;
llong findClosest(llong x)
{
    int l = -1, r = v.size(), mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (v[mid].second <= x) l = mid;
        else r = mid;
    }

    assert(l != -1);
    return v[l].second;
}

llong calcMAX(llong x)
{
    if (dp.count(x))
    {
        return dp[x];
    }

    assert(inInterval(x));
    if (x < d)
    {
        return x * a;
    }

    int idx = getInterval(x);
    if (x - v[idx].first >= d)
    {
        llong times = (x - v[idx].first) / d;
        return dp[x] = calcMAX(x - times * d) + times * b;
    }

    if (inInterval(x - d))
    {
        dp[x] = calcMAX(x - d) + b;
    } else
    {   
        llong closest = findClosest(x - d);
        dp[x] = calcMAX(closest) + b + (x - closest - d) * a;
    }

    return dp[x];
}

void solve()
{
    v.push_back(inp[0]);
    inp.erase(inp.begin());
    for (const auto &[l, r] : inp)
    {
        int ll = -1, rr = v.size(), mid;
        while (ll < rr - 1)
        {
            mid = (ll + rr) / 2;
            if (v[mid].second + d < l) ll = mid;
            else rr = mid;
        }

        if (rr != v.size() && std::max(v[rr].first + d, l) <= r)
        {
            minJumps[v.size()] = minJumps[rr] + 1;
            v.push_back({std::max(v[rr].first + d, l), r});
        } 
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        llong x;
        std::cin >> x;
        if (inInterval(x))
        {
            int r = getInterval(x);
            std::cout << std::min(calcMAX(x), a * (x - minJumps[r] * d) + b * minJumps[r]) << '\n';
        } else
        {
            std::cout << -1 << '\n';
        }
    }
}

void input()
{
    std::cin >> n >> q;
    std::cin >> d >> a >> b;

    llong last = -1;
    for (int i = 1 ; i <= n ; ++i)
    {
        llong l, r;
        std::cin >> l >> r;
        if (last + 1 < l) inp.push_back({last + 1, l - 1});
        last = r;
    }

    if (last < INF) inp.push_back({last + 1, INF});
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'bool inInterval(llong)':
Main.cpp:31:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     return r != v.size() && v[r].first <= x;
      |            ~~^~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:108:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         if (rr != v.size() && std::max(v[rr].first + d, l) <= r)
      |             ~~~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 38 / 38
• Subtask 3: 25 / 25
• Subtask 4: 32 / 32