Submission #849835

#	Time	Username	Problem	Language	Result	Execution time	Memory
849835		Essa2006	Overtaking (IOI23_overtaking)	C++17	19 / 100	273 ms	73688 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)
ll n, x, m, l;
set<array<ll, 3> >st;
vector<map<ll, ll> >Cnv, Done;
vector<vector<ll> > E, TT, End;
vector<vector<array<ll, 2> > >Mx;
vector<vector<array<ll, 2> > >Has;
vector<ll> Ta, Wa, Sa;
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), Done.resize(m+1);
    for(int i=0;i<n;i++){
        ll y=TT[i][0];
        if(!Done[0][y]++){
            array<ll, 2>a={y, 0};
            Cnv[0][y]=Has[0].size()-1;
            Has[0].push_back(a);
            
        }
//        ll nxt=max(Mx[0][i][1], y+x*(Sa[0+1]-Sa[0]));
//        {
//            array<ll, 2>a={nxt, 0};
//            Has[1].push_back(a);
//            nxt=TT[i][1];
//            Cnv[1][nxt]=Has[1].size();
//        }
//        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]));
            if(!Done[j+1][nxt]++){
                array<ll, 2>a={nxt, 0};
                Cnv[j+1][nxt]=Has[j+1].size();
                Has[j+1].push_back(a);
            }
            if(i<n && !Done[j+1][TT[i][j+1]]++){
                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<array<ll, 2> >Events;
    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];
            if(l>r)
                continue;
            ll mx=Has[j+1][Cnv[j+1][TT[i][j+1]]][1];
            {
                array<ll, 2>a={l, -mx};
                Events.push_back(a);
            }
            array<ll, 2>a={r, mx};
            Events.push_back(a);
        }
    }
    multiset<ll>Mx;
    sort(all(Events));
    ll LL=-1;
    for(int i=0;i<Events.size();i++){
        bool del=(Events[i][1]>0);
        if(!del)
            Events[i][1]*=-1;
        if(del){
            Mx.erase(Mx.find(Events[i][1]));
            if(Mx.empty() || Events[i][1]>*Mx.rbegin() && LL!=-1){
                array<ll, 3>a={LL, Events[i][0], Events[i][1]};
                st.insert(a);
                LL=-1;
            }
        }
        else{
            if(!Mx.empty() && Events[i][1]>*Mx.rbegin() && LL!=-1 && LL<Events[i][0]){
                array<ll, 3>a={LL, Events[i][0]-1, *Mx.rbegin()};
                st.insert(a);
                LL=-1;
            }
            Mx.insert(Events[i][1]);
            if(LL==-1)
                LL=Events[i][0];
        }
    }
    
}
 
ll arrival_time(ll Y){
    ll y=Y, ans=y;
    array<ll, 3>a={y, (ll)2e18, (ll)2e18};
    if(st.empty()){
        return y+x*l;
    }
    auto it=st.upper_bound(a);
    if(it==st.begin())
        return y+x*l;
    it--;
    a=*it;
    if(y<=a[1])
        ans=a[2];
    if(ans==y)
        ans+=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:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<T.size();i++){
      |                 ~^~~~~~~~~
overtaking.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
overtaking.cpp:174: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]
  174 |         for(int i=0;i<Has[j].size();i++){
      |                     ~^~~~~~~~~~~~~~
overtaking.cpp:202: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]
  202 |     for(int i=0;i<Has[m-1].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
overtaking.cpp:207: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]
  207 |         for(int i=0;i<Has[j].size();i++){
      |                     ~^~~~~~~~~~~~~~
overtaking.cpp:244: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]
  244 |     for(int i=0;i<Events.size();i++){
      |                 ~^~~~~~~~~~~~~~
overtaking.cpp:250:56: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  250 |             if(Mx.empty() || Events[i][1]>*Mx.rbegin() && LL!=-1){

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