제출 #1220694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220694		cpdreamer	추월 (IOI23_overtaking)	C++17	65 / 100	3596 ms	47200 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = (ll)1e9+7;
#define P pair
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
struct station {
    ll t;
    ll w;
};
bool sorted(station a,station b) {
    if (a.t==b.t) {
        return a.w<b.w;
    }
    return a.t<b.t;
}
station a[1001][1001],e[1001][1001];
ll s[1001];
int n,m;
ll x;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    x=X;
    n=N,m=M;
    for (int i=0;i<N;i++) {
        a[0][i].t=T[i];
        a[0][i].w=W[i];
    }
    for (int i=0;i<M;i++) {
        s[i]=S[i];
    }
    sort(a[0],a[0]+N,sorted);
    for (int i=0;i<M-1;i++) {
        for (int j=0;j<N;j++) {
            e[i+1][j].t=a[i][j].t+(S[i+1]-S[i])*a[i][j].w;
            e[i+1][j].w=a[i][j].w;
        }
        ll maxd[N];
        maxd[0]=e[i+1][0].t;
        for (int j=1;j<N;j++) {
            maxd[j]=max(maxd[j-1],e[i+1][j].t);
        }
        for (int j=0;j<N;j++) {
            a[i+1][j].t=maxd[j];
            a[i+1][j].w=a[i][j].w;
        }
        sort(a[i+1],a[i+1]+N,sorted);
    }
}

long long arrival_time(long long Y)
{
    ll ans=Y;
    int curr=-1;
    for (int i=0;i<n;i++) {
        if (a[0][i].t<Y || (a[0][i].t==Y && a[0][i].w<x)) {
            curr++;
        }
    }
    for (int i=1;i<m;i++) {
        ll b=((s[i]-s[i-1])*x)+ans;
        if (curr!=-1) {
            b=max(b,a[i][curr].t);
        }
        ans=b;
        int l=0,r=curr;
        int f=-1;
        while (l<=r) {
            int mid=l+(r-l)/2;
            if (a[i][mid].t==b && a[i][mid].w>x) {
                f=mid;
                r=mid-1;
            }
            else
                l=mid+1;
        }
        if (f!=-1) {
            curr=f-1;
        }
    }
    return ans;
}

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