Submission #1135406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135406		nvmdava	Overtaking (IOI23_overtaking)	C++20	39 / 100	3593 ms	45040 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
vector<pair<ll, ll>> car;
int n;

vector<vector<ll>> arr;
vector<ll> s;
int m;
ll x;
         //  true->fixed
         //  false +add
map<ll, pair<bool, ll> > seg;
map<ll, pair<bool, ll> > segtmp;
map<ll, pair<bool, ll> > segtmp2;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    for(int i = 0; i < N; ++i) {
        if (X < W[i]) {
            car.push_back({T[i], W[i]});
        }
    }
    x = X;
    n = car.size();

    sort(car.begin(), car.end());
    arr.push_back(vector<ll>{});
    for (int j = 0; j < n; ++j) {
        arr.back().push_back(car[j].first);
      //  std::cout<<car[j].first<<" ";
    }
    arr.back().push_back(2'100'000'000'000'000'000);
    //std::cout<<std::endl;
    m = M;
    s.push_back(S[0]);
    
    for (int i = 1; i < M; ++i) {
        for(int j = 0; j < n; ++j) {
            car[j].first += car[j].second * (S[i] - S[i - 1]);
        }
        for (int j = 1; j < n; ++j) {
            car[j].first = max(car[j].first, car[j - 1].first);
        }

        sort(car.begin(), car.end());
        arr.push_back(vector<ll>{});
        for (int j = 0; j < n; ++j) {
            arr.back().push_back(car[j].first);
         //   std::cout<<car[j].first<<" ";
        }
        arr.back().push_back(2'100'000'000'000'000'000);
        //std::cout<<std::endl;
        s.push_back(S[i]);
    }

    seg[1'000'000'000'000'000'000LL] = {false, 0};

    for(int i = 1; i < m; ++i) {
        segtmp.clear();
        int j = -1;
        ll b_old = seg.begin()->second.second;
        for(auto& [key, value] : seg ) {
            if (value.first) {
                ll e_old = value.second;
                while (arr[i - 1][j + 1] < e_old) {
                    ++j;
                }

                if (j == -1) {
                    b_old = e_old + 1;
                    segtmp[key] = {true, e_old + x * (s[i] - s[i - 1])};
                } else {
                    b_old = e_old + 1;
                    segtmp[key] = {true, max(e_old + x * (s[i] - s[i - 1]), arr[i][j])};
                }
            } else {
                ll e_old = value.second + key;
                assert (b_old <= e_old);
                while(arr[i - 1][j + 1] < b_old) {
                    ++j;
                }

                if (j == -1) {
                    ll tar_old = min(arr[i - 1][j + 1], e_old);
                    segtmp[tar_old - value.second] = {false, value.second + x * (s[i] - s[i - 1])};
                    b_old = tar_old + 1;
                    if (arr[i - 1][j + 1] >= e_old) continue;
                    ++j;
                }

                while(arr[i - 1][j] < e_old) {
                    ll tar_old = min({arr[i - 1][j + 1], e_old, arr[i][j] - x * (s[i] - s[i - 1])});
                    if (tar_old >= b_old) {
                        segtmp[tar_old - value.second] = {true, arr[i][j]};
                        b_old = tar_old + 1;
                    }
                    ll next_old = min({arr[i - 1][j + 1], e_old});
                    if (next_old >= b_old) {
                        segtmp[next_old - value.second] = {false, value.second + x * (s[i] - s[i - 1])};
                        b_old = next_old + 1;
                    }
                    if (arr[i - 1][j + 1] >= e_old) break;
                    ++j;
                }
            }
        }
        swap(seg, segtmp);
        // for(auto& [key, value] : seg) {
        //     cout<<key<<" "<<value.first<<" "<<value.second<<std::endl;
        // }
        // cout<<std::endl;
    }

    return;
}

long long arrival_time(long long Y)
{
    auto it = seg.lower_bound(Y);
    return it->second.first ? it->second.second : it->second.second + Y;
}

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