Submission #849718

#	Time	Username	Problem	Language	Result	Execution time	Memory
849718		Essa2006	Overtaking (IOI23_overtaking)	C++17	9 / 100	120 ms	305112 KiB

overtaking

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#include "overtaking.h"
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int pr=24, s_p=(1<<pr), e_p=(1<<(pr+1))-1;
ll n, x, m, l, cur;
map<ll, ll>nw, ld;
set<array<ll, 4> >st;
vector<map<ll, ll> >Cnv(m+1);
vector<vector<ll> > E, TT, End;
vector<vector<array<ll, 2> > >Mx;
vector<vector<array<ll, 2> > >Has;
vector<ll> Ta, Wa, Sa, Smx(1<<(pr+1));
 
void update(int id, int u, int v, ll c, int l, int r){
    if(l>v || r<u)
        return;
    if(l>=u && r<=v){
        Smx[id]=max(Smx[id], c);
        return;
    }
    int md=(l+r)/2;
    update(id*2, u, v, c, l, md);
    update(id*2+1, u, v, c, md+1, r);
}
 
void get(int id, int u, int v, int l, int r){
    assert(v-u<=1);
    if(!(l<=u && r>=v))
        return;
    cur=max(cur, Smx[id]);
    if(l==r)
        return;
    int md=(l+r)/2;
    get(id*2, u, v, l, md);
    get(id*2+1, u, v, md+1, r);
}
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
    n=N, x=X, m=M, l=L;
    for(int i=0;i<T.size();i++){
        if(W[i]>x){
            Ta.push_back(T[i]);
            Wa.push_back(W[i]);
        }
        else{
            n--;
        }
    }
    for(int i=0;i<S.size();i++){
        Sa.push_back(S[i]);
    }
    E.resize(n+1, vector<ll>(m+1)), TT=E, End.resize(m+1, vector<ll>(n+1));
    Mx.resize(m+1, vector<array<ll, 2> >(n+1));
    map<int, int>Ind;
    vector<array<ll, 3> >Help_(n);
    for(int i=0;i<n;i++){
        TT[i][0]=Ta[i];
        array<ll, 3>a={TT[i][0], i, (ll)0};
        Help_[i]=a;
    }
    sort(all(Help_));
    for(int j=1;j<m;j++){
        for(int i=0;i<n;i++){
            E[i][j]=TT[i][j-1]+Wa[i]*(Sa[j]-Sa[j-1]);
            TT[i][j]=E[i][j];
        }
        ll real_mx=0, last_mx=0;
        for(int i=0;i<n;i++){
            if(!i || Help_[i][0]!=Help_[i-1][0])
                Help_[i][2]=real_mx, last_mx=real_mx;
            real_mx=max(real_mx, E[Help_[i][1]][j]);
            Help_[i][2]=max(Help_[i][2], last_mx);
            Ind[Help_[i][1]]=i;
        }
        vector<array<ll, 3> >New_(n);
        for(int i=0;i<n;i++){
            TT[i][j]=max(TT[i][j], Help_[Ind[i]][2]);
            array<ll, 3>a={TT[i][j], i, (ll)0};
            New_[i]=a;
        }
        ll mx=0;
        for(int i=0;i<n;i++){
            mx=max(mx, TT[Help_[i][1]][j]);
            array<ll, 2>a={Help_[i][0], mx};
            Mx[j-1][i]=a;
        }
        Help_=New_;
        sort(all(Help_));
    }
    Cnv.resize(m+1), Has.resize(m+1);
    for(int i=0;i<n;i++){
        ll y=TT[i][0];
        {
            array<ll, 2>a={y, 0};
            Has[0].push_back(a);
        }
        Cnv[0][y]=Has[0].size()-1;
        ll nxt=max(Mx[0][i][1], y+x*(Sa[0+1]-Sa[0]));
        Cnv[1][nxt]=Has[1].size();
        {
            array<ll, 2>a={nxt, 0};
            Has[1].push_back(a);
            nxt=TT[i][1];
        }
        Cnv[1][nxt]=Has[1].size();
        array<ll, 2>a={nxt, 0};
        Has[1].push_back(a);
    }
    for(int j=0;j<m-1;j++){
        // when will I finish if I reach this station at time y
        for(int i=0;i<Has[j].size();i++){
            ll y=Has[j][i][0], nxt=0;
            // find the maximum for the time that is before me
            int l=0, r=n-1, res=-1;
            while(l<=r){
                int md=(l+r)/2;
                if(Mx[j][md][0]>=y)
                    r=md-1;
                else
                    res=md, l=md+1;
            }
            if(res!=-1){
                nxt=Mx[j][res][1];
            }
            nxt=max(nxt, y+x*(Sa[j+1]-S[j]));
            {
                array<ll, 2>a={nxt, 0};
                Cnv[j+1][nxt]=Has[j+1].size();
                Has[j+1].push_back(a);
            }
            if(i<n){
                nxt=TT[i][j+1];
                array<ll, 2>a={nxt, 0};
                Cnv[j+1][nxt]=Has[j+1].size();
                Has[j+1].push_back(a);
            }
        }
    }
    for(int i=0;i<Has[m-1].size();i++){
        Has[m-1][i][1]=Has[m-1][i][0];
    }
    for(int j=m-2;j>=0;j--){
        // when will I finish if I reach this station at time y
        for(int i=0;i<Has[j].size();i++){
            ll y=Has[j][i][0], nxt=0;
            // find the maximum for the time that is before me
            int l=0, r=n-1, res=-1;
            while(l<=r){
                int md=(l+r)/2;
                if(Mx[j][md][0]>=y)
                    r=md-1;
                else
                    res=md, l=md+1;
            }
            if(res!=-1){
                nxt=Mx[j][res][1];
            }
            nxt=max(nxt, y+x*(Sa[j+1]-S[j]));
            Has[j][i][1]=Has[j+1][Cnv[j+1][nxt]][1];
        }
    }
    vector<ll>All;
    for(int j=0;j<m-1;j++){
        for(int i=0;i<n;i++){
            ll l=TT[i][j]-x*Sa[j]+1;;
            ll r=TT[i][j+1]-x*Sa[j+1];
            ll mx=Has[j+1][Cnv[j+1][TT[i][j+1]]][1];
            All.push_back(l);
            All.push_back(r);
            array<ll, 4>a={l, r, mx, j};
            st.insert(a);
        }
    }
    sort(all(All));
    int cur=0;
    for(int i=0;i<All.size();i++){
        if(!i || All[i]!=All[i-1])
            nw[All[i]]=cur, ld[cur]=All[i], cur++;
    }
    for(auto a:st){
        update(1, nw[a[0]]+s_p, nw[a[1]]+s_p, a[2], s_p, e_p);
    }
}
 
ll arrival_time(ll Y){
    ll y=Y, ans=y;
    cur=0;
    ll L=0, rr=ld.size()-1, res=-1;
    while(L<=rr){
        ll md=(L+rr)/2;
        if(ld[md]<=y)
            res=md, L=md+1;
        else
            rr=md-1;
    }
    if(res!=-1 || (res==ld.size()-1 && ld[res]!=y))
        get(1, res+s_p, res+(ld[res]!=y)+s_p, s_p, e_p);
    ans=max(ans, cur);
    if(ans==y)
        ans=y+x*l;
    return ans;
}
//int main()
//{
//    int L, N, X, M, Q;
//    assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
//    std::vector<long long> T(N);
//    for (int i = 0; i < N; i++)
//        assert(1 == scanf("%lld", &T[i]));
//    std::vector<int> W(N);
//    for (int i = 0; i < N; i++)
//        assert(1 == scanf("%d", &W[i]));
//    std::vector<int> S(M);
//    for (int i = 0; i < M; i++)
//        assert(1 == scanf("%d", &S[i]));
//    std::vector<long long> Y(Q);
//    for (int i = 0; i < Q; i++)
//        assert(1 == scanf("%lld", &Y[i]));
//
//    fclose(stdin);
//
//    init(L, N, T, W, X, M, S);
//    std::vector<long long> res(Q);
//    for (int i = 0; i < Q; i++)
//        res[i] = arrival_time(Y[i]);
//
//    for (int i = 0; i < Q; i++)
//        printf("%lld\n", res[i]);
//    fclose(stdout);
//    return 0;
//}

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:128:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i=0;i<T.size();i++){
      |                 ~^~~~~~~~~
overtaking.cpp:137:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
overtaking.cpp:199:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |         for(int i=0;i<Has[j].size();i++){
      |                     ~^~~~~~~~~~~~~~
overtaking.cpp:227:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |     for(int i=0;i<Has[m-1].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
overtaking.cpp:232:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |         for(int i=0;i<Has[j].size();i++){
      |                     ~^~~~~~~~~~~~~~
overtaking.cpp:264:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  264 |     for(int i=0;i<All.size();i++){
      |                 ~^~~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:284:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  284 |     if(res!=-1 || (res==ld.size()-1 && ld[res]!=y))
      |                    ~~~^~~~~~~~~~~~~

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