제출 #1089736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1089736		lighton	추월 (IOI23_overtaking)	C++17	100 / 100	791 ms	118868 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
vector<vector<ll> > state;
vector<vector<ll> > dp;
vector<vector<vector<ll> > > num;
vector<vector<ll> > h;
vector<ll> vel,st;
vector<int> s;
ll add;
int n,m;

struct Line{
    ll a,b;
    ll get(ll x){
        return a*x+b;
    }
};
struct Frac{
    __int128 a,b;
    bool operator>=(const Frac &r) const{
        return a*r.b >= r.a*b;
    }
};
Frac cross(Line x , Line y){
    if(x.a-y.a > 0) return {y.b-x.b,x.a-y.a};
    else return {-y.b+x.b,-x.a+y.a};
}
struct CHT{
    deque<Line> lines;
    deque<Frac> st;
    void add(Line x){
        while(lines.size() && lines.front().a <= x.a) lines.pop_front(),st.pop_front();
        while(lines.size() >=2 && cross(lines.front(),x) >= st[1]) lines.pop_front(),st.pop_front();
        if(lines.size()){
            st.front() = cross(x,lines.front());
            st.push_front({-inf,1});
        }
        else st.push_front({-inf,1});
        lines.push_front(x);
    }
    pair<ll,ll> nxt(ll y){
        if(lines.empty()) return {m,y};
        int l = 0, r=st.size(),mid;
        while(l+1<r){
            mid=l+r>>1;
            if(cross(lines[mid],{0,y}) >= st[mid]) l=mid;
            else r=mid;
        }
        Frac res = cross(lines[l],{0,y});

        l=0,r=m;
        while(l+1<r){
            mid=l+r>>1;
            Frac tmp = {s[mid],1};
            if(tmp >= res) r=mid;
            else l=mid;
        }
        if(r==m) return {m,y};
        ll ret1 = r;
        ll x = s[r];

        l = 0,r=st.size();
        while(l+1<r){
            mid = l+r>>1;
            Frac tmp = {x,1};
            if(tmp >= st[mid]) l=mid;
            else r=mid;
        }
        return {ret1,lines[l].get(x)};
    }
};
vector<CHT> beg;



void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    s=S;
    forf(i,0,N-1) if(W[i]-X > 0) vel.pb(W[i]-X), st.pb(T[i]);
    add = ((ll)X)*L;

    m = s.size();
    n = vel.size();
    state.resize(m,{}),dp.resize(m,{}),num.resize(m,{});
    h.resize(n,vector<ll>(m,0));

    forf(i, 0, n - 1) h[i][0] = st[i];
    forf(i, 0, n - 1) state[0].pb(h[i][0]);
    sort(all(state[0])), comp(state[0]);
    dp[0].resize(state[0].size()), num[0].resize(state[0].size());
    forf(i, 0, n - 1) num[0][idx(h[i][0], state[0])].pb(i);

    forf(i, 0, m - 2) {
        ll pmx = 0;
        ll delta = s[i + 1] - s[i];
        forf(j, 0, (int) state[i].size() - 1) {
            ll now = state[i][j];
            ll tmp = 0;
            for (int idx: num[i][j]) {
                ll nxt = max(now + delta * vel[idx], pmx);
                tmp = max(nxt, tmp);
                h[idx][i + 1] = nxt;
                state[i + 1].pb(nxt);
            }
            pmx = max(pmx, tmp);
            dp[i][j] = pmx;
        }

        sort(all(state[i + 1])), comp(state[i + 1]);
        int sz = state[i + 1].size();
        dp[i + 1].resize(sz), num[i + 1].resize(sz,{});
        forf(j, 0, n - 1) num[i + 1][idx(h[j][i + 1], state[i + 1])].pb(j);
    }

    beg.resize(state[0].size());
    forb(i,m-1,0){
        CHT cht;
        forf(j,0,(int)state[i].size()-1){
            ll now = state[i][j];
            auto [nxt,y] = cht.nxt(now);

            if(nxt==m) dp[i][j] = y;
            else dp[i][j] = dp[nxt][idx(y,state[nxt])];
            for(int idx : num[i][j]) cht.add({vel[idx],h[idx][i]-s[i]*vel[idx]});
            if(i==0) beg[j] = cht;
        }
    }

}

long long arrival_time(long long Y)
{
    ll now = Y;
    int j = lower_bound(all(state[0]),now)-state[0].begin()-1;
    if(j == -1) return now+add;
    auto [nxt,y] = beg[j].nxt(now);
    if(nxt==m) return y+add;
    else return dp[nxt][idx(y,state[nxt])]+add;
}

컴파일 시 표준 에러 (stderr) 메시지

overtaking.cpp: In member function 'std::pair<long long int, long long int> CHT::nxt(ll)':
overtaking.cpp:59:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |             mid=l+r>>1;
      |                 ~^~
overtaking.cpp:67:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |             mid=l+r>>1;
      |                 ~^~
overtaking.cpp:78:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |             mid = l+r>>1;
      |                   ~^~

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