Submission #1010057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010057		boris_mihov	Overtaking (IOI23_overtaking)	C++17	100 / 100	2985 ms	81528 KiB

overtaking

#include "overtaking.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
 
typedef long long llong;
const int MAXN = 1000 + 10;
const int MAXQ = 5000 + 10;
const int BUCKET_SIZE = 32;

llong x;
int n, m, l;
struct SegmentTree
{
    llong tree[4 * MAXN];
    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node] = 1e18;
            return;
        }

        int mid = l + r >> 1;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);
        tree[node] = std::min(tree[2*node], tree[2*node + 1]);
    }

    void update(int l, int r, int node, int queryPos, llong queryVal)
    {
        if (l == r)
        {
            tree[node] = std::min(tree[node], queryVal);
            return;
        }

        int mid = l + r >> 1;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
        else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
        tree[node] = std::min(tree[2*node], tree[2*node + 1]);
    }

    int search(int l, int r, int node, int queryL, int queryR, llong queryVal)
    {
        if (queryR < l || r < queryL || tree[node] >= queryVal)
        {
            return -1;
        }

        if (l == r)
        {
            return l;
        }

        int mid = l + r >> 1;
        int res = search(l, mid, 2*node, queryL, queryR, queryVal);
        if (res != -1) return res;
        return search(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
    }

    void build()
    {
        build(0, m - 2, 1);
    }

    void update(int pos, llong val)
    {
        update(0, m - 2, 1, pos, val);
    }

    int search(int l, int r, llong val)
    {
        return search(0, m - 2, 1, l, r, val); 
    }
};

SegmentTree tree;
std::vector <int> s;
std::vector <std::pair <llong,int>> buses;
std::vector <std::pair <llong,llong>> t[MAXN];
std::vector <std::pair <llong,llong>> continueThrough[MAXN];
std::vector <std::pair <llong,llong>> intervals[BUCKET_SIZE];
std::vector <llong> ifBegining[MAXN];

int findIntersection(int pos, llong time)
{
    int l = 0, r = t[pos].size(), mid;
    while (l < r - 1)
    {
        mid = l + r >> 1;
        if (t[pos][mid].first < time) l = mid;
        else r = mid;
    }
 
    return l;
}
 
long long my_arrival_time(int pos, llong time)
{
    for (int i = pos ; i + 1 < m ; ++i)
    {
        int l = 0, r = t[i].size(), mid;
        while (l < r - 1)
        {
            mid = l + r >> 1;
            if (t[i][mid].first < time) l = mid;
            else r = mid;
        }   
 
        time = std::max(time + 1LL * x * (s[i + 1] - s[i]), t[i][l].second);
    }
 
    return time;
}
 
void init(int L, int N, std::vector <long long> T, std::vector <int> W, int X, int M, std::vector <int> S)
{
    n = N;
    m = M;
    s = S;
    x = X;
 
    for (int i = 0 ; i < n ; ++i)
    {
        buses.push_back({T[i], W[i]});
    }
 
    for (int i = 0 ; i + 1 < m ; ++i)
    {
        t[i].push_back({-1, 0});
        std::vector <std::pair <llong,int>> newBuses;
        std::sort(buses.begin(), buses.end());
        for (const auto &[time, w] : buses)
        {
            llong arrive = 1LL * (s[i + 1] - s[i]) * w + time;
            if (arrive > t[i].back().second)
            {
                t[i].push_back({time, arrive});
            }
 
            newBuses.push_back({t[i].back().second, w});
        }
 
        buses = newBuses;
    }
 
    std::vector <std::pair <int,int>> v;
    for (int i = 0 ; i + 1 < m ; ++i)
    {
        for (int j = 1 ; j < t[i].size() ; ++j)
        {
            v.push_back({i, j});
        }
    }
 
    std::sort(v.begin(), v.end(), [&](auto &a, auto &b)
    {
        return t[a.first][a.second].second - 1LL * s[a.first + 1] * x > t[b.first][b.second].second - 1LL * s[b.first + 1] * x;
    });
 
    for (int i = 0 ; i + 1 < m ; ++i)
    {
        ifBegining[i].resize(t[i].size());
        continueThrough[i].push_back({1e18, 0});
    }
    
    tree.build();
    for (const auto &[i, j] : v)
    {
        bool done = false;
        ifBegining[i][j] = 1LL * (s[m - 1] - s[i + 1]) * x + t[i][j].second;
        int u = tree.search(i + 1, m - 1, t[i][j].second - 1LL * s[i + 1] * x);
        if (u != -1)
        {
            int l = 0, r = t[u].size(), mid;
            while (l < r - 1)
            {
                mid = l + r >> 1;
                if (!ifBegining[u][mid]) l = mid;
                else if (t[i][j].second - 1LL * s[i + 1] * x <= t[u][mid].first - 1LL * s[u] * x) r = mid;
                else l = mid;
            }

            ifBegining[i][j] = ifBegining[u][l];
        }
 
        tree.update(i, t[i][j].first - 1LL * s[i] * x);
    }

    for (int i = 0 ; i + 1 < m ; ++i)
    {
        for (int j = 1 ; j < t[i].size() ; ++j)
        {
            if (t[i][j].first - 1LL * x * s[i] + 1 > t[i][j].second - 1LL * x * s[i + 1] - 1)
            {
                continue;
            }

            // std::cout << "intersect with: " << i << ' ' << t[i][j].first << ' ' << t[i][j].second << " if: " << t[i][j].first - 1LL * x * s[i] + 1 << ' ' << t[i][j].second - 1LL * x * s[i + 1] - 1 << '\n';
            intervals[i / BUCKET_SIZE].push_back({t[i][j].first - 1LL * x * s[i] + 1, t[i][j].second - 1LL * x * s[i + 1] - 1});
        }
    }

    for (int i = 0 ; i < BUCKET_SIZE ; ++i)
    {
        if (intervals[i].empty())
        {
            continue;
        }

        std::vector <std::pair <llong,llong>> curr;
        std::sort(intervals[i].begin(), intervals[i].end());
        curr.push_back(intervals[i][0]);

        for (int j = 1 ; j < intervals[i].size() ; ++j)
        {
            if (intervals[i][j].first <= curr.back().second)
            {
                curr.back().second = std::max(curr.back().second, intervals[i][j].second);
            } else
            {
                curr.push_back(intervals[i][j]);
            }
        }

        intervals[i] = curr;
    }
}
 
long long arrival_time(llong time)
{
    int idx = 0;
    int bucket = 0;
    while (idx < m - 1)
    {
        int l = -1, r = intervals[bucket].size(), mid;
        while (l < r - 1)
        {
            mid = l + r >> 1;
            if (intervals[bucket][mid].first <= time) l = mid;
            else r = mid;
        }

        if (l != -1 && time <= intervals[bucket][l].second)
        {
            break;
        }

        idx += BUCKET_SIZE;
        bucket++;
    }

    if (idx >= m - 1)
    {
        return 1LL * x * s[m - 1] + time;
    }

    for (int i = idx ; i + 1 < m ; ++i)
    {
        int l = 0, r = t[i].size(), mid;
        while (l < r - 1)
        {
            mid = l + r >> 1;
            if (t[i][mid].first < time + 1LL * x * s[i]) l = mid;
            else r = mid;
        }   

        if (l != 0 && time + 1LL * x * s[i + 1] < t[i][l].second)
        {
            return ifBegining[i][l];
        }
    }
 
    return 1LL *  x * s[m - 1] + time;
}

Compilation message (stderr)

overtaking.cpp: In member function 'void SegmentTree::build(int, int, int)':
overtaking.cpp:26:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         int mid = l + r >> 1;
      |                   ~~^~~
overtaking.cpp: In member function 'void SegmentTree::update(int, int, int, int, llong)':
overtaking.cpp:40:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int mid = l + r >> 1;
      |                   ~~^~~
overtaking.cpp: In member function 'int SegmentTree::search(int, int, int, int, int, llong)':
overtaking.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = l + r >> 1;
      |                   ~~^~~
overtaking.cpp: In function 'int findIntersection(int, llong)':
overtaking.cpp:93:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         mid = l + r >> 1;
      |               ~~^~~
overtaking.cpp: In function 'long long int my_arrival_time(int, llong)':
overtaking.cpp:108:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |             mid = l + r >> 1;
      |                   ~~^~~
overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:153:28: 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]
  153 |         for (int j = 1 ; j < t[i].size() ; ++j)
      |                          ~~^~~~~~~~~~~~~
overtaking.cpp:181:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  181 |                 mid = l + r >> 1;
      |                       ~~^~~
overtaking.cpp:173:14: warning: unused variable 'done' [-Wunused-variable]
  173 |         bool done = false;
      |              ^~~~
overtaking.cpp:195:28: 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]
  195 |         for (int j = 1 ; j < t[i].size() ; ++j)
      |                          ~~^~~~~~~~~~~~~
overtaking.cpp:218:28: 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]
  218 |         for (int j = 1 ; j < intervals[i].size() ; ++j)
      |                          ~~^~~~~~~~~~~~~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(llong)':
overtaking.cpp:242:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  242 |             mid = l + r >> 1;
      |                   ~~^~~
overtaking.cpp:266:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  266 |             mid = l + r >> 1;
      |                   ~~^~~

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 35 / 35