Submission #843046

#	Time	Username	Problem	Language	Result	Execution time	Memory
843046		abcvuitunggio	Overtaking (IOI23_overtaking)	C++17	0 / 100	1 ms	10584 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF=3e18;
typedef pair <long long, long long> pii;
typedef pair <pii, long long> piii;
pii st[32000001];
vector <long long> ve;
vector <piii> v;
long long e[1001][1001],l[1001][1001],r[1001][1001],x,n,t[1001],w[1001],d;
void update(int node, int l, int r, int u, int v, pii p){
    if (ve[l]>v||ve[r]<u||l>r||u>v)
        return;
    if (ve[l]>=u&&ve[r]<=v){
        st[node]=min(st[node],p);
        return;
    }
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v,p);
    update(node<<1|1,mid+1,r,u,v,p);
}
pii get(int node, int l, int r, long long i){
    pii p={INF,i};
    while (l<r&&ve[l]<=i&&ve[r]>=i){
        p=min(p,st[node]);
        int mid=(l+r)>>1;
        if (ve[mid]>=i){
            r=mid;
            node<<=1;
        }
        else if (ve[mid+1]<=i){
            l=mid+1;
            node=node<<1|1;
        }
        else
            break;
    }
    return min(p,st[node]);
}
void init(int L, int N, vector<long long> T, vector<int> W, int X, int m, vector<int> s)
{
    d=L;
    x=X;
    for (int i=0;i<N;i++){
        if (W[i]>x){
            w[n]=W[i];
            e[n][0]=t[n]=T[i];
            n++;
        }
    }
    for (int i=1;i<m;i++){
        for (int j=0;j<n;j++)
            v.push_back({{e[j][i-1],w[j]},j});
        sort(v.begin(),v.end());
        long long mx=0;
        for (int it=0;it<v.size();it++){
            int j=v[it].second;
            mx=max(mx,e[j][i-1]+w[j]*(s[i]-s[i-1]));
            e[j][i]=mx;
            l[j][i-1]=e[j][i-1]+1;
            r[j][i-1]=min((it==v.size()-1?INF:e[v[it+1].second][i-1]),mx-x*(s[i]-s[i-1]));
            ve.push_back(l[j][i-1]+x*(d-s[i-1]));
            ve.push_back(l[j][i-1]+x*(d-s[i-1])-1);
            ve.push_back(l[j][i-1]+x*(d-s[i-1])+1);
            ve.push_back(r[j][i-1]+x*(d-s[i-1]));
            ve.push_back(r[j][i-1]+x*(d-s[i-1])-1);
            ve.push_back(r[j][i-1]+x*(d-s[i-1])+1);
            //cout << i-1 << ' ' << j << ' ' << l[j][i-1] << ' ' << r[j][i-1] << '\n';
        }
        v.clear();
    }
    for (int i=0;i<n;i++){
        ve.push_back(e[i][m-1]);
        ve.push_back(e[i][m-1]-1);
        ve.push_back(e[i][m-1]+1);
    }
    ve.push_back(INF);
    sort(ve.begin(),ve.end());
    ve.resize(unique(ve.begin(),ve.end())-ve.begin());
    for (int i=1;i<=ve.size()*4;i++)
        st[i]={INF,INF};
    for (int i=m-1;i;i--){
        for (int j=0;j<n;j++)
            v.push_back({{e[j][i],w[j]},j});
        sort(v.begin(),v.end());
        for (auto p:v){
            int j=p.second;
            auto q=get(1,0,ve.size()-1,e[j][i]+x*(d-s[i]));
            update(1,0,ve.size()-1,l[j][i-1]+x*(d-s[i-1]),r[j][i-1]+x*(d-s[i-1]),{i,q.second});
        }
        v.clear();
    }
    return;
}

long long arrival_time(long long y)
{
    int val=lower_bound(ve.begin(),ve.end(),y+x*d)-ve.begin();
    auto res=get(1,0,ve.size()-1,ve[val]);
    return (res.first==INF?y+x*d:res.second);
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:56:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int it=0;it<v.size();it++){
      |                       ~~^~~~~~~~~
overtaking.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             r[j][i-1]=min((it==v.size()-1?INF:e[v[it+1].second][i-1]),mx-x*(s[i]-s[i-1]));
      |                            ~~^~~~~~~~~~~~
overtaking.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i=1;i<=ve.size()*4;i++)
      |                  ~^~~~~~~~~~~~~

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