제출 #845241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
845241		Alfraganus	추월 (IOI23_overtaking)	C++17	9 / 100	7 ms	604 KiB

overtaking

#include "overtaking.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
typedef tree<ll, null_type, greater_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> Javohir;
#define fs first
#define ss second

vector<Javohir> a;
ll n, m, x;
vector<ll> s;

void init(int l, int a1, vector<ll> T, vector<int> w, int a2, int a3, vector<int> a4){
    n = a1;
    m = a3;
    x = a2;
    for(int i = 0; i < m; i ++)
        s.push_back(a4[i]);
    vector<vector<ll>> e(m, vector<ll> (n)), t(m, vector<ll> (n));
    a.resize(m);
    for(int i = 0; i < n; i ++)
        t[0][i] = T[i], a[0].insert(T[i]), e[0][i] = T[i];
    for(int i = 1; i < m; i ++){
        Javohir v;
        for(int j = 0; j < n; j ++)
            e[i][j] = t[i - 1][j] + w[j] * (s[i] - s[i - 1]), v.insert(e[i][j]);
        for(int j = 0; j < n; j ++){
            ll k = a[i - 1].order_of_key(e[i - 1][j] - 1);
            ll ans = e[i][j];
            if(k < n)
                ans = max(ans, *v.find_by_order(k));
            t[i][j] = ans;
            a[i].insert(ans);
        }
    }
}

ll arrival_time(ll y){
    for(int i = 1; i < m; i ++){
        ll e = y + x * (s[i] - s[i - 1]);
        ll k = a[i - 1].order_of_key(y - 1);
        if(k >= n)
            y = e;
        else
            y = max(e, *a[i].find_by_order(k));
    }
    return y;
}

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