Submission #849317

#	Time	Username	Problem	Language	Result	Execution time	Memory
849317		Essa2006	Overtaking (IOI23_overtaking)	C++17	Compilation error	0 ms	0 KiB

overtaking

//#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<ll> Ta, Wa, Sa;
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;
 
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];
        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();
        a={nxt, 0};
        Has[1].push_bac(a);
    }
    for(int j=1;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=y+x*(Sa[j+1]-Sa[j]);
            else{
                nxt=Mx[j][res][1];
            }
            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];
            a={nxt, 0};
            Cnv[j+1][nxt]=Has[j+1].size();
        }
    }
    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=y+x*(Sa[j+1]-Sa[j]);
            else{
                nxt=Mx[j][res][1];
            }
            Has[j][i][1]=Has[j+1][Cnv[j+1][nxt]][1];
        }
    }
    for(int j=0;j<m-1;j++){
        for(int i=0;i<n;i++){
            ll l=((TT[i][j])*(Wa[i]-x)+Wa[i]-1)/Wa[i];
            l+=((TT[i][j])*(Wa[i]-x)/Wa[i]==l);
            ll r=(TT[i][j+1])*(Wa[i]-x)/Wa[i];
            ll mx=Has[j+1][Cnv[j+1][TT[i][j+1]]][1];
            array<ll, 3>a={l, r, mx};
            st.insert(a);
        }
    }
    vector<array<ll, 3> >Sim;
    for(auto a:st){
        Sim.push_back(a);
    }
    st.clear();
    int mn_l=0, mx_r=-1, cur_mx=0;
    for(int i=0;i<Sim.size();i++){
        ll l=Sim[i][0], r=Sim[i][1], mx=Sim[i][2];
        if(mx_r==-1){
            mn_l=l, mx_r=r, cur_mx=mx;
            continue;
        }
        if(l>mx_r){
            array<ll, 3>a={mn_l, mx_r, cur_mx};
            st.insert(a);
            mn_l=l, mx_r=r, cur_mx=mx;
            continue;
        }
        if(mx>cur_mx){
            array<ll, 3>a={mn_l, l-1, cur_mx};
            st.insert(a);
            mn_l=l, mx_r=max(mx_r), cur_mx=mx;
            continue;
        }
        
    }
    return;
}

ll arrival_time(ll Y){
    ll y=Y;
    array<ll, 3>a={y, 0, 0};
    a=*st.lower_bound(a);
    ll ans=a[2];
    return ans;
}

Compilation message (stderr)

overtaking.cpp:10:1: error: 'set' does not name a type
   10 | set<array<ll, 3> >st;
      | ^~~
overtaking.cpp:11:1: error: 'vector' does not name a type
   11 | vector<ll> Ta, Wa, Sa;
      | ^~~~~~
overtaking.cpp:12:1: error: 'vector' does not name a type
   12 | vector<map<ll, ll> >Cnv(m+1);
      | ^~~~~~
overtaking.cpp:13:1: error: 'vector' does not name a type
   13 | vector<vector<ll> > E, TT, End;
      | ^~~~~~
overtaking.cpp:14:1: error: 'vector' does not name a type
   14 | vector<vector<array<ll, 2> > >Mx;
      | ^~~~~~
overtaking.cpp:15:1: error: 'vector' does not name a type
   15 | vector<vector<array<ll, 2> > >Has;
      | ^~~~~~
overtaking.cpp:17:25: error: 'vector' has not been declared
   17 | void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
      |                         ^~~~~~
overtaking.cpp:17:31: error: expected ',' or '...' before '<' token
   17 | void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
      |                               ^
overtaking.cpp: In function 'void init(int, int, int)':
overtaking.cpp:18:12: error: 'X' was not declared in this scope
   18 |     n=N, x=X, m=M, l=L;
      |            ^
overtaking.cpp:18:17: error: 'M' was not declared in this scope
   18 |     n=N, x=X, m=M, l=L;
      |                 ^
overtaking.cpp:19:19: error: 'T' was not declared in this scope
   19 |     for(int i=0;i<T.size();i++){
      |                   ^
overtaking.cpp:20:12: error: 'W' was not declared in this scope
   20 |         if(W[i]<x){
      |            ^
overtaking.cpp:21:13: error: 'Ta' was not declared in this scope
   21 |             Ta.push_back(T[i]);
      |             ^~
overtaking.cpp:22:13: error: 'Wa' was not declared in this scope
   22 |             Wa.push_back(W[i]);
      |             ^~
overtaking.cpp:28:19: error: 'S' was not declared in this scope
   28 |     for(int i=0;i<S.size();i++){
      |                   ^
overtaking.cpp:29:9: error: 'Sa' was not declared in this scope; did you mean 'SS'?
   29 |         Sa.push_back(S[i]);
      |         ^~
      |         SS
overtaking.cpp:31:5: error: 'E' was not declared in this scope
   31 |     E.resize(n+1, vector<ll>(m+1)), TT=E, End.resize(m+1, vector<ll>(n+1));
      |     ^
overtaking.cpp:31:19: error: 'vector' was not declared in this scope
   31 |     E.resize(n+1, vector<ll>(m+1)), TT=E, End.resize(m+1, vector<ll>(n+1));
      |                   ^~~~~~
overtaking.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | //#include "overtaking.h"
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:31:26: note: in expansion of macro 'll'
   31 |     E.resize(n+1, vector<ll>(m+1)), TT=E, End.resize(m+1, vector<ll>(n+1));
      |                          ^~
overtaking.cpp:31:37: error: 'TT' was not declared in this scope
   31 |     E.resize(n+1, vector<ll>(m+1)), TT=E, End.resize(m+1, vector<ll>(n+1));
      |                                     ^~
overtaking.cpp:31:43: error: 'End' was not declared in this scope
   31 |     E.resize(n+1, vector<ll>(m+1)), TT=E, End.resize(m+1, vector<ll>(n+1));
      |                                           ^~~
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:31:66: note: in expansion of macro 'll'
   31 |     E.resize(n+1, vector<ll>(m+1)), TT=E, End.resize(m+1, vector<ll>(n+1));
      |                                                                  ^~
overtaking.cpp:32:5: error: 'Mx' was not declared in this scope; did you mean 'x'?
   32 |     Mx.resize(m+1, vector<array<ll, 2> >(n+1));
      |     ^~
      |     x
overtaking.cpp:32:27: error: 'array' was not declared in this scope
   32 |     Mx.resize(m+1, vector<array<ll, 2> >(n+1));
      |                           ^~~~~
overtaking.cpp:1:1: note: 'std::array' is defined in header '<array>'; did you forget to '#include <array>'?
  +++ |+#include <array>
    1 | //#include "overtaking.h"
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:32:33: note: in expansion of macro 'll'
   32 |     Mx.resize(m+1, vector<array<ll, 2> >(n+1));
      |                                 ^~
overtaking.cpp:32:40: error: expected primary-expression before '>' token
   32 |     Mx.resize(m+1, vector<array<ll, 2> >(n+1));
      |                                        ^
overtaking.cpp:33:5: error: 'map' was not declared in this scope
   33 |     map<int, int>Ind;
      |     ^~~
overtaking.cpp:1:1: note: 'std::map' is defined in header '<map>'; did you forget to '#include <map>'?
  +++ |+#include <map>
    1 | //#include "overtaking.h"
overtaking.cpp:33:9: error: expected primary-expression before 'int'
   33 |     map<int, int>Ind;
      |         ^~~
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:34:18: note: in expansion of macro 'll'
   34 |     vector<array<ll, 3> >Help_(n);
      |                  ^~
overtaking.cpp:36:18: error: 'Ta' was not declared in this scope
   36 |         TT[i][0]=Ta[i];
      |                  ^~
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:37:15: note: in expansion of macro 'll'
   37 |         array<ll, 3>a={TT[i][0], i, (ll)0};
      |               ^~
overtaking.cpp:38:9: error: 'Help_' was not declared in this scope
   38 |         Help_[i]=a;
      |         ^~~~~
overtaking.cpp:38:18: error: 'a' was not declared in this scope
   38 |         Help_[i]=a;
      |                  ^
overtaking.cpp:40:14: error: 'Help_' was not declared in this scope
   40 |     sort(all(Help_));
      |              ^~~~~
overtaking.cpp:7:16: note: in definition of macro 'all'
    7 | #define all(a) a.begin(), a.end()
      |                ^
overtaking.cpp:40:5: error: 'sort' was not declared in this scope; did you mean 'short'?
   40 |     sort(all(Help_));
      |     ^~~~
      |     short
overtaking.cpp:43:32: error: 'Wa' was not declared in this scope
   43 |             E[i][j]=TT[i][j-1]+Wa[i]*(Sa[j]-Sa[j-1]);
      |                                ^~
overtaking.cpp:43:39: error: 'Sa' was not declared in this scope; did you mean 'SS'?
   43 |             E[i][j]=TT[i][j-1]+Wa[i]*(Sa[j]-Sa[j-1]);
      |                                       ^~
      |                                       SS
overtaking.cpp:50:21: error: 'max' was not declared in this scope
   50 |             real_mx=max(real_mx, E[Help_[i][1]][j]);
      |                     ^~~
overtaking.cpp:52:13: error: 'Ind' was not declared in this scope
   52 |             Ind[Help_[i][1]]=i;
      |             ^~~
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:54:22: note: in expansion of macro 'll'
   54 |         vector<array<ll, 3> >New_(n);
      |                      ^~
overtaking.cpp:56:42: error: 'Ind' was not declared in this scope
   56 |             TT[i][j]=max(TT[i][j], Help_[Ind[i]][2]);
      |                                          ^~~
overtaking.cpp:56:22: error: 'max' was not declared in this scope
   56 |             TT[i][j]=max(TT[i][j], Help_[Ind[i]][2]);
      |                      ^~~
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:57:19: note: in expansion of macro 'll'
   57 |             array<ll, 3>a={TT[i][j], i, (ll)0};
      |                   ^~
overtaking.cpp:58:13: error: 'New_' was not declared in this scope
   58 |             New_[i]=a;
      |             ^~~~
overtaking.cpp:58:21: error: 'a' was not declared in this scope
   58 |             New_[i]=a;
      |                     ^
overtaking.cpp:62:16: error: 'max' was not declared in this scope; did you mean 'mx'?
   62 |             mx=max(mx, TT[Help_[i][1]][j]);
      |                ^~~
      |                mx
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:63:19: note: in expansion of macro 'll'
   63 |             array<ll, 2>a={Help_[i][0], mx};
      |                   ^~
overtaking.cpp:64:24: error: 'a' was not declared in this scope
   64 |             Mx[j-1][i]=a;
      |                        ^
overtaking.cpp:66:15: error: 'New_' was not declared in this scope
   66 |         Help_=New_;
      |               ^~~~
overtaking.cpp:69:5: error: 'Cnv' was not declared in this scope
   69 |     Cnv.resize(m+1), Has.resize(m+1);
      |     ^~~
overtaking.cpp:69:22: error: 'Has' was not declared in this scope
   69 |     Cnv.resize(m+1), Has.resize(m+1);
      |                      ^~~
overtaking.cpp:72:38: error: 'Sa' was not declared in this scope; did you mean 'SS'?
   72 |         ll nxt=max(Mx[0][i][1], y+x*(Sa[0+1]-Sa[0]));
      |                                      ^~
      |                                      SS
overtaking.cpp:72:16: error: 'max' was not declared in this scope
   72 |         ll nxt=max(Mx[0][i][1], y+x*(Sa[0+1]-Sa[0]));
      |                ^~~
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:74:15: note: in expansion of macro 'll'
   74 |         array<ll, 2>a={nxt, 0};
      |               ^~
overtaking.cpp:75:26: error: 'a' was not declared in this scope
   75 |         Has[1].push_back(a);
      |                          ^
overtaking.cpp:95:17: error: 'nxt' was not declared in this scope
   95 |                 nxt=y+x*(Sa[j+1]-Sa[j]);
      |                 ^~~
overtaking.cpp:95:26: error: 'Sa' was not declared in this scope; did you mean 'SS'?
   95 |                 nxt=y+x*(Sa[j+1]-Sa[j]);
      |                          ^~
      |                          SS
overtaking.cpp:97:17: error: 'nxt' was not declared in this scope
   97 |                 nxt=Mx[j][res][1];
      |                 ^~~
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:99:19: note: in expansion of macro 'll'
   99 |             array<ll, 2>a={nxt, 0};
      |                   ^~
overtaking.cpp:100:22: error: 'nxt' was not declared in this scope
  100 |             Cnv[j+1][nxt]=Has[j+1].size();
      |                      ^~~
overtaking.cpp:101:32: error: 'a' was not declared in this scope
  101 |             Has[j+1].push_back(a);
      |                                ^
overtaking.cpp:125:17: error: 'nxt' was not declared in this scope
  125 |                 nxt=y+x*(Sa[j+1]-Sa[j]);
      |                 ^~~
overtaking.cpp:125:26: error: 'Sa' was not declared in this scope; did you mean 'SS'?
  125 |                 nxt=y+x*(Sa[j+1]-Sa[j]);
      |                          ^~
      |                          SS
overtaking.cpp:127:17: error: 'nxt' was not declared in this scope
  127 |                 nxt=Mx[j][res][1];
      |                 ^~~
overtaking.cpp:129:44: error: 'nxt' was not declared in this scope
  129 |             Has[j][i][1]=Has[j+1][Cnv[j+1][nxt]][1];
      |                                            ^~~
overtaking.cpp:134:31: error: 'Wa' was not declared in this scope
  134 |             ll l=((TT[i][j])*(Wa[i]-x)+Wa[i]-1)/Wa[i];
      |                               ^~
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:138:19: note: in expansion of macro 'll'
  138 |             array<ll, 3>a={l, r, mx};
      |                   ^~
overtaking.cpp:139:13: error: 'st' was not declared in this scope; did you mean 'std'?
  139 |             st.insert(a);
      |             ^~
      |             std
overtaking.cpp:139:23: error: 'a' was not declared in this scope
  139 |             st.insert(a);
      |                       ^
overtaking.cpp:136:16: warning: unused variable 'r' [-Wunused-variable]
  136 |             ll r=(TT[i][j+1])*(Wa[i]-x)/Wa[i];
      |                ^
overtaking.cpp:137:16: warning: unused variable 'mx' [-Wunused-variable]
  137 |             ll mx=Has[j+1][Cnv[j+1][TT[i][j+1]]][1];
      |                ^~
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:142:18: note: in expansion of macro 'll'
  142 |     vector<array<ll, 3> >Sim;
      |                  ^~
overtaking.cpp:143:16: error: 'st' was not declared in this scope; did you mean 'std'?
  143 |     for(auto a:st){
      |                ^~
      |                std
overtaking.cpp:144:9: error: 'Sim' was not declared in this scope
  144 |         Sim.push_back(a);
      |         ^~~
overtaking.cpp:146:5: error: 'st' was not declared in this scope; did you mean 'std'?
  146 |     st.clear();
      |     ^~
      |     std
overtaking.cpp:148:19: error: 'Sim' was not declared in this scope
  148 |     for(int i=0;i<Sim.size();i++){
      |                   ^~~
overtaking.cpp:151:26: error: 'r' was not declared in this scope
  151 |             mn_l=l, mx_r=r, cur_mx=mx;
      |                          ^
overtaking.cpp:151:36: error: 'mx' was not declared in this scope; did you mean 'm'?
  151 |             mn_l=l, mx_r=r, cur_mx=mx;
      |                                    ^~
      |                                    m
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:155:19: note: in expansion of macro 'll'
  155 |             array<ll, 3>a={mn_l, mx_r, cur_mx};
      |                   ^~
overtaking.cpp:156:23: error: 'a' was not declared in this scope
  156 |             st.insert(a);
      |                       ^
overtaking.cpp:157:26: error: 'r' was not declared in this scope
  157 |             mn_l=l, mx_r=r, cur_mx=mx;
      |                          ^
overtaking.cpp:157:36: error: 'mx' was not declared in this scope; did you mean 'm'?
  157 |             mn_l=l, mx_r=r, cur_mx=mx;
      |                                    ^~
      |                                    m
overtaking.cpp:160:12: error: 'mx' was not declared in this scope; did you mean 'm'?
  160 |         if(mx>cur_mx){
      |            ^~
      |            m
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:161:19: note: in expansion of macro 'll'
  161 |             array<ll, 3>a={mn_l, l-1, cur_mx};
      |                   ^~
overtaking.cpp:162:23: error: 'a' was not declared in this scope
  162 |             st.insert(a);
      |                       ^
overtaking.cpp:163:26: error: 'max' was not declared in this scope
  163 |             mn_l=l, mx_r=max(mx_r), cur_mx=mx;
      |                          ^~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:173:5: error: 'array' was not declared in this scope
  173 |     array<ll, 3>a={y, 0, 0};
      |     ^~~~~
overtaking.cpp:173:5: note: 'std::array' is defined in header '<array>'; did you forget to '#include <array>'?
overtaking.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
overtaking.cpp:173:11: note: in expansion of macro 'll'
  173 |     array<ll, 3>a={y, 0, 0};
      |           ^~
overtaking.cpp:174:5: error: 'a' was not declared in this scope
  174 |     a=*st.lower_bound(a);
      |     ^
overtaking.cpp:174:8: error: 'st' was not declared in this scope; did you mean 'std'?
  174 |     a=*st.lower_bound(a);
      |        ^~
      |        std
overtaking.cpp:172:8: warning: unused variable 'y' [-Wunused-variable]
  172 |     ll y=Y;
      |        ^