Submission #1103032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103032		Ludissey	Overtaking (IOI23_overtaking)	C++17	0 / 100	1 ms	340 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
int n,X,m;
vector<pair<int,int>> b;
vector<vector<int>> s; // time of bus i a la station j
vector<vector<pair<int,int>>> sb; // sorted array of busses i at station
vector<vector<int>> dp; // when it will arrive if it collides at n
vector<int> a;
vector<pair<pair<int,int>,int>> fseg;

void init(signed L, signed N, std::vector<long long> T, std::vector<signed> W, signed _x, signed M, std::vector<signed> _s)
{
    n=N; X=_x; m=M;
    a.resize(m+1);
    sb.resize(m+1);
    a[m]=L;
    for (int i = 0; i < m; i++) a[i]=_s[i];
    for (int i = 0; i < n; i++) {
        if(W[i]<X) continue;
        b.push_back({W[i],T[i]});
    }
    n=sz(b);
    s.resize(n, vector<int>(m+1));
    sort(rall(b));
    for (int i = 0; i < n; i++) { sb[0].push_back({b[i].second,i}); s[i][0]=b[i].second; }
    for (int i = 1; i < m; i++)
    {
        sort(all(sb[i-1]));
        int mx=0;
        int cmx=0;
        for (int j = 0; j < n; j++)
        {
            int x=sb[i-1][j].second;
            if(j>0&&sb[i-1][j].first!=sb[i-1][j-1].first){
                mx=max(mx,cmx);
                cmx=mx;
            }
            s[x][i]=max(mx,sb[i-1][j].first+b[x].first*(a[i]-a[i-1]));
            cmx=max(s[x][i],cmx);
            sb[i].push_back({s[x][i],x});    
        }
    }
    

    vector<pair<int,pair<int,int>>> seg;

    for (int i = m-1; i > 0; i--)
    {
        for (int j = 0; j < n; j++)
        {
            int x=sb[i-1][j].second;
            int xd=a[m]-a[i];
            int _l=s[x][i]-(X*a[i]),r=s[x][i-1]-(X*a[i-1]),w=s[x][i]+X*xd;
            seg.push_back({w,{_l,r}});
        }
    }
    unordered_map<int,int> comp;
    unordered_map<int,int> decomp;
    set<int> st;
    for (int i = 0; i < sz(seg); i++)
    {
        st.insert(seg[i].second.first);
        st.insert(seg[i].second.second);
    }
    int j=0;
    for (auto u : st)
    {
        comp[u]=j;
        decomp[j]=u;
        j++;
    }
    vector<vector<int>> event(j);
    for (int i = 0; i < sz(seg); i++){
        event[comp[seg[i].second.first]].push_back(i);
        event[comp[seg[i].second.second]].push_back(-(i+1));
    }
    priority_queue<pair<int,int>> pq;
    vector<bool> rem(sz(seg),false);
    int lmx=-1;
    int lI=0;
    for (int i = j-1; i >= 0; i--)
    {
        for (auto u : event[i])
        {
            if(u<0) rem[abs(u)-1]=true;
            else pq.push({seg[u].first,u});
        }
        while(!pq.empty()){
            if(rem[pq.top().second]) pq.pop();
            else break;
        }
        if(pq.empty()){
            if(lmx>-1) fseg.push_back({{decomp[lI],decomp[i]},lmx});
            lmx=-1;
        }else if(lmx!=pq.top().first){
            if(lmx>-1){
                fseg.push_back({{decomp[lI],decomp[i]},lmx});
            }
            lmx=pq.top().first;
            lI=i;
        }
    }
    sort(rall(fseg));
    return;
}

long long arrival_time(long long Y) 
{
    int l=0; int r=sz(fseg)-1;
    int ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(fseg[mid].first.first>=Y){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    if(ans==-1||fseg[ans].first.second>=Y) return (a[m]*X);
    return fseg[ans].second;
}

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