Submission #842203

#TimeUsernameProblemLanguageResultExecution timeMemory
8422037modyOvertaking (IOI23_overtaking)C++17
0 / 100
0 ms348 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<pair<ll,ll>> arr; vector<vector<ll>> s; vector<vector<pair<ll,ll>>> a; vector<ll> station; ll all,n,x,m; void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) { n=N;all=L;x=X;m=M;; for(int i=0; i < n;i++){ if(W[i] > x && T[i]<=1e9){ arr.push_back({W[i],(ll)T[i]}); } } n=arr.size(); s.resize(m); station.resize(m); for(int i=0; i < m;i++){ station[i]=ll(S[i]); } sort(arr.begin(),arr.end()); reverse(arr.begin(),arr.end()); for(int i=0; i < m;i++){ s[i].resize(n); } a.resize(m); for(int i=0; i < n;i++) s[0][i]=arr[i].second; for(int i=1; i < m;i++){ ll length=S[i]-S[i-1]; set<pair<ll,ll>> st; for(int j=0; j < n;j++){ ll start=s[i-1][j]; ll expected=start+(arr[j].first * length); ll actual=expected; auto it=st.lower_bound({start,0}); if(it!=st.begin()){ it--; pair<ll,ll> curr=*it; if(start > curr.first && curr.second > actual) actual=curr.second; } s[i][j]=actual; st.insert({start,actual}); } vector<pair<ll,ll>> curr(n); for(int j=0; j < n;j++){ curr[j]={s[i-1][j],s[i][j]}; } sort(curr.begin(),curr.end()); a[i]=curr; } // for(auto c : a){ // for(auto g : c) cout << g.first << ' ' << g.second << " "; // cout << endl; // } } long long arrival_time(long long Y) { ll ans=Y; for(int i=1; i < m;i++){ ll length = station[i]-station[i-1]; ll start = ans; ll expected = start + (x*length); ll actual=expected; int l=0,r=n-1; int id=-1; while(l<=r){ int mid=(l+r)/2; if(a[i][mid].first < start) id=mid,l=mid+1; else r=mid-1; } if(id!=-1){ pair<ll,ll> curr=a[i][id]; // cout << curr.first << ' ' << curr.second << ' ' << start << ' ' << actual << endl; if(start > curr.first && curr.second > actual) actual=curr.second; } ans=actual; } return ans; } // void solve(){ // int l,q; cin >> l >> n >> x >> m >> q; // vector<ll> T(n); // vector<int> W(n); // for(int i=0; i < n;i++) cin >> T[i]; // for(int i=0; i < n;i++) cin >> W[i]; // vector<int> S(m); // for(int i=0; i < m;i++) cin >> S[i]; // init(l,n,T,W,x,m,S); // while(q--){ // ll temp; cin >> temp; // cout << arrival_time(temp) << endl; // } // } // int main(){ // ios::sync_with_stdio(false); // cin.tie(NULL); // cout.tie(NULL); // int t=1; // // cin >> t; // while(t--) solve(); // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...