Submission #847805

#	Time	Username	Problem	Language	Result	Execution time	Memory
847805		emad234	Overtaking (IOI23_overtaking)	C++17	0 / 100	1 ms	348 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;
}
int n;
struct lst{
  vector<tim>v;
};
lst a[4001];
ll x;
int m;
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 = N;
  for(int i = 0;i < N;i++){
    a[0].v.push_back({T[i],T[i] + (ll)(S[1] - S[0]) * (ll)W[i],i});
  }
  sort(a[0].v.begin(),a[0].v.end());
  for(int 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 = t + (S[i + 1] - S[i]) * W[id];
      a[i].v.push_back({t,e,id});
    }
    sort(a[i].v.begin(),a[i].v.end());
  }
  // 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)(s[1] - s[0]) * (ll)x,n};
    for(int i = 1;i < m;i++){
      // ans.log();
      ll mx = ans.exp;
      for(auto x : a[i - 1].v){
        if(x.time < ans.time) mx = max(x.exp,mx);
        else break;
      }
      if(i == m - 1) return mx;
      ans = {mx,mx + ll(s[i + 1] - s[i]) * (ll)x,n};
    }
}


// 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 'long long int arrival_time(long long int)':
overtaking.cpp:79:1: warning: control reaches end of non-void function [-Wreturn-type]
   79 | }
      | ^

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