Submission #1135398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135398		nvmdava	Overtaking (IOI23_overtaking)	C++20	0 / 100	1 ms	328 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 = seg.begin()->second.second;
        for(auto& [key, value] : seg ) {
            if (value.first) {
                ll e = value.second;
                while (arr[i - 1][j + 1] < e) {
                    ++j;
                }
                if (j == -1) {
                    e += x * (s[i] - s[i - 1]); 
                } else {
                    e = max(e + x * (s[i] - s[i - 1]), arr[i][j]);
                }
                segtmp[key] = {true, e};
                b = e + 1;
            } else {
                ll e = value.second + key;
                while (arr[i - 1][j + 1] < b) {
                    ++j;
                }
                
                if (j == -1) {
                    ll next = min(arr[i - 1][j + 1] - value.second, key);
                    segtmp[next] = {value.first, value.second + x * (s[i] - s[i - 1])};
                    b = next + 1;
                    if (next == key) continue;
                    ++j;
                }

                while (arr[i - 1][j] < e) {
                    if (j >= 0) {
                        ll tar = arr[i][j] - x * (s[i] - s[i - 1]) - value.second;
                        if (b <= tar) {
                            segtmp[min(tar, key)] = {true, arr[i][j]};
                            b = min(tar, key) + 1;
                        }
                        ll next = min(arr[i - 1][j + 1], e);
                        if (next >= b) {
                            segtmp[next] = {false, value.second + x * (s[i] - s[i - 1])};
                            b = next + 1;
                        }
                    } else {
                        ll next = min(arr[i - 1][j + 1], e);
                        segtmp[next] = {false, value.second + x * (s[i] - s[i - 1])};
                        b = next + 1;
                    }
                    if (arr[i - 1][j + 1] < e) {
                        ++j;
                    } else {
                        break;
                    }
                }
                b = e + 1;
            }
        }
        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: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35