Submission #848377

#	Time	Username	Problem	Language	Result	Execution time	Memory
848377		Essa2006	Overtaking (IOI23_overtaking)	C++17	65 / 100	3531 ms	33360 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, y, m, l;
vector<ll> Ta, Wa, Sa;
vector<vector<ll> > E, TT;
vector<vector<array<ll, 2> > >Mx;
 
void init(int L, int N, vector<ll> t, vector<int> w, int X, int M, vector<int> s){
    l=L, n=N, x=X, m=M;
    for(int i=0;i<t.size();i++){
        Ta.push_back(t[i]);
    }
    for(int i=0;i<w.size();i++){
        Wa.push_back(w[i]);
    }
    for(int i=0;i<s.size();i++){
        Sa.push_back(s[i]);
    }
    E.resize(n+1, vector<ll>(m+1)), TT=E;
    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};
            if(i && Help_[i][0]<Help_[i-1][0])
                n/=0;
            Mx[j-1][i]=a;
        }
        Help_=New_;
        sort(all(Help_));
        
    }
    return;
}
 
ll arrival_time(ll Y){
    ll y=Y;
    for(int j=0;j<m-1;j++){
        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)
            y+=(Sa[j+1]-Sa[j])*x;
        else{
            y=max(y+(Sa[j+1]-Sa[j])*x, Mx[j][res][1]);
        }
    }
    return y;
}
//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:100:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i=0;i<t.size();i++){
      |                 ~^~~~~~~~~
overtaking.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
overtaking.cpp:106:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
overtaking.cpp:143:18: warning: division by zero [-Wdiv-by-zero]
  143 |                 n/=0;
      |                 ~^~~

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