Submission #847830

#	Time	Username	Problem	Language	Result	Execution time	Memory
847830		emad234	Overtaking (IOI23_overtaking)	C++17	65 / 100	3543 ms	401884 KiB

overtaking

#include <bits/stdc++.h>
typedef long long ll;
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll mxN = 1e5 + 2;
using namespace std;
struct tim{
  ll time,exp,i;
  void log(){
    cout<<"{ "<<time<<" , "<<exp<<" , "<<i<<" }  ";
  }
};
bool operator>(tim c, tim b){
  return c.time > b.time;
}
bool operator<(tim c, tim b){
  return c.time < b.time;
}
tim mxtm(tim a,tim b){
  if(a.exp >= b.exp) return a;
  else return b;
}
int n;
struct lst{
  vector<tim>v;
  tim seg[4001];
  void update(int ind,tim val){
    ind += n;
    seg[ind] = val;
    ind /= 2;
    while(ind){
      seg[ind] = mxtm(seg[ind * 2],seg[ind * 2 + 1]);
      ind /= 2;
    }
  }
  tim query(int l,int r,int s,int e,int ind){
    if(l > e || r < s) return {-1,-1,-1};
    if(l >= s && r <= e) return seg[ind];
    int md = (l + r) / 2;
    return mxtm(query(l,md,s,e,ind * 2),query(md + 1,r,s,e,ind * 2 + 1));
  }
  void build(){
    for(int i = 0;i < v.size();i++){
      update(i,v[i]);
    }
  }
  ll find(tim a){
    ll x = lower_bound(v.begin(),v.end(),a) - v.begin();
    x--;
    // cout<<x<<' ';a.log();
    // cout<<'\n';
    if(x == -1){
      return a.exp;
    }
    auto ans = query(1,n,1,x + 1,1);
    return max(a.exp,ans.exp);
  }
};
lst a[4001];
ll x;
ll m;
ll n1;
vector<int>s;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
  m = M;
  x = ll(X);
  s = S;
  n = exp2(ceil(log2(N)));
  n1 = n;
  for(int i = 0;i < N;i++){
    a[0].v.push_back({T[i],ll(T[i] + ll((ll)(S[1] - S[0]) * (ll)W[i])),i});
  }
  sort(a[0].v.begin(),a[0].v.end());
  a[0].build();
  for(ll i = 1;i < M - 1;i++){
    ll mx = 0;
    ll prev = -1;
    queue<ll>q;
    for(auto x : a[i - 1].v){
      if(x.time != prev){
        while(q.size()){
          mx = max(mx,q.front());
          q.pop();
        }
      }
      q.push(x.exp);
      prev = x.time;
      ll t = max(mx,x.exp);
      ll id = x.i;
      ll e = ll(t + (ll)((ll)(S[i + 1] - S[i]) * (ll)(W[id])));
      a[i].v.push_back({t,e,id});
    }
    sort(a[i].v.begin(),a[i].v.end());
    a[i].build();
  }
  // for(int i = 0;i < M - 1;i++){
  //   for(auto x : a[i].v){
  //     x.log();
  //   }
  //   cout<<'\n';
  // }
}

long long arrival_time(long long Y)
{
    tim ans = {Y,(ll)(Y + (ll)((ll)(s[1] - s[0]) * (ll)x)),n1};
    for(ll i = 1;i < m;i++){
      // ans.log();
      ll mx = max(a[i-1].find(ans),ans.exp);
      if(i == m - 1) return mx;
      ans = {mx,mx + (ll)(s[i + 1] - s[i]) * (ll)x,n1};
    }
}

// 
// 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 member function 'void lst::build()':
overtaking.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<tim>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0;i < v.size();i++){
      |                   ~~^~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
  115 | }
      | ^

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