제출 #845340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
845340		Alfraganus	추월 (IOI23_overtaking)	C++17	19 / 100	6 ms	1624 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;
typedef tree<pair<ll, ll>, null_type, less_equal<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> other_one;
#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<other_one> v(m);
    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], v[0].insert({T[i], i});
    for(int i = 1; i < m; i ++){
        for(int j = 0; j < n; j ++)
            e[i][j] = t[i - 1][j] + w[j] * (s[i] - s[i - 1]);
        int j = 0;
        ll mx = 0;
        for(auto x : v[i - 1]){
            ll ans = max(e[i][x.ss], mx);
            t[i][x.ss] = ans;
            a[i].insert(ans);
            v[i].insert({ans, x.ss});
            mx = max(mx, e[i][x.ss]);
            j++;
        }
    }
}

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: 10 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35