Submission #841854

#	Time	Username	Problem	Language	Result	Execution time	Memory
841854		lucaperju	Overtaking (IOI23_overtaking)	C++17	100 / 100	3328 ms	294992 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
long long t[1003][1003],e[1003][1003];
long long ord[1003],cj;
bool cmp (int a, int b)
{
    if(t[a][cj-1] < t[b][cj-1])
        return true;
    if(t[a][cj-1] > t[b][cj-1])
        return false;
    return e[a][cj] < e[b][cj];
}
struct ura
{
    long long l,r,x;
};
vector<ura>vc;
bool cmp2 (ura a, ura b)
{
    if(a.x == b.x)
    {
        return a.r < b.r;
    }
    return a.x>b.x;
}
vector<long long>coords;
vector<long long>norms;
unordered_map<long long,int>invnorm;
long long aint[16000005];
long long realcoords[4000005];
void upd (int nod, int l, int r, int ul, int ur, long long val)
{
    if(ul<=l && r <= ur)
    {
        aint[nod] = max(aint[nod],val);
        return;
    }
    if(ur < l || r < ul)
        return;
    int mid = ((l+r)>>1);
    upd(nod<<1,l,mid,ul,ur,val);
    upd((nod<<1)|1,mid+1,r,ul,ur,val);
}
long long qry (int nod, int l, int r, int pz)
{
    if(pz < l || r < pz)
        return 0;
    if(l == r)
        return aint[nod];
    int mid = ((l+r)>>1);
    long long a = max(qry(nod<<1,l,mid,pz), qry((nod<<1)|1,mid+1,r,pz));
    return max(a, aint[nod]);
}
void build (int nod, int l, int r)
{
    if(l == r)
    {
        aint[nod] = realcoords[l];
        return;
    }
    int mid = ((l+r)>>1);
    build(nod<<1,l,mid);
    build((nod<<1)|1,mid+1,r);
}
long long xx,kk,ll;
long long idkk,okt;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    ll = L;
    xx = X;
    int i,j;
    for(i=0;i<N;++i)
        t[i][0] = T[i];
    for(i=0;i<N;++i)
        ord[i]=i;
    for(j = 1; j < M; ++j)
    {
        for(i = 0 ; i < N; ++i)
        {
            e[i][j] = t[i][j-1] + W[i] * 1LL * (S[j] - S[j-1]);
          //  cout<<i<<' '<<t[i][j-1]<<' '<<W[i]<<' '<<S[j]<<' '<<S[j-1]<<' '<<e[i][j]<<'\n';
        }
        cj = j;
        sort(ord,ord+N,cmp);
        long long mxc = 0;
        for(i = 0; i < N; ++i)
        {
            int vlc = ord[i];
           // cout<<vlc<<' ';
            mxc = max(mxc, e[vlc][j]);
            t[vlc][j] = mxc; 
        }
    }
    for(i = 0; i < N; ++i)
    {
        for(j = 1; j < M; ++j)
        {
            ura x;
            x.l = t[i][j-1] - S[j-1]*1LL*X + 1;
            x.r = t[i][j] - S[j]*1LL*X;
            x.x = j;
            if(x.l > x.r)
                continue;
            vc.push_back(x);
            coords.push_back(x.l);
            coords.push_back(x.r);
        }
       // cout<<'\n';
    }
    if(coords.empty())
    {
        okt = 1;
        return;
    }
    sort(coords.begin(),coords.end());
    long long k = 1;
    norms.push_back(1);
    invnorm[coords[0]] = 1;
    realcoords[1] = coords[0];
    for(int i = 1; i < coords.size(); ++i)
    {
        if(coords[i] != coords[i-1])
            k+=2;
   //     cout<<"coord: "<<coords[i]<<'\n';
        invnorm[coords[i]] = k;
        realcoords[k] = coords[i];
        norms.push_back(k);
    }
   // cout<<"\n\n";
    build(1,1,k);
    sort(vc.begin(),vc.end(),cmp2);
    for(int i = 0; i < vc.size();++i)
    {
        ura x = vc[i];
        int l = invnorm[x.l];
        int r = invnorm[x.r];
        long long val = qry(1,1,k,r);
      //  cout<<"upd "<<x.x<<' '<<l<<' '<<r<<' '<<val<<'\n';
        upd(1,1,k,l,r,val);
    }
    kk = k;
}

long long arrival_time(long long Y)
{
    if(okt)
    {
        return Y + ll * 1LL * xx;
    }
    int pas = (1<<21);
    int pz = -1;
    while(pas)
    {
        if(pz+pas < (int)coords.size() && coords[pz+pas]<=Y)
            pz += pas;
        pas>>=1;
    }
    if(pz == -1)
    {
        return Y + ll * 1LL * xx;
    }
    if(pz == (int)coords.size()-1 && Y >= coords[pz])
        return Y + ll * 1LL * xx;
    //cout<<"here "<<pz<<'\n';
    if(coords[pz] == Y)
    {
        //cout<<invnorm[3]<<"<-\n";
        //cout<<"idk "<<qry(1,1,kk,invnorm[coords[pz]])<<'\n';
        return max(Y,qry(1,1,kk,invnorm[coords[pz]])) + ll * 1LL * xx;
    }
    else
    {
        return max(Y,qry(1,1,kk,invnorm[coords[pz]] + 1)) + ll * 1LL * xx;
    }
}
/*
3 1 3 2 7
2
4
0 3
1 2 3 4 5 6 7
*/

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:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i = 1; i < coords.size(); ++i)
      |                    ~~^~~~~~~~~~~~~~~
overtaking.cpp:133:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ura>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for(int i = 0; i < vc.size();++i)
      |                    ~~^~~~~~~~~~~

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