Submission #844732

#TimeUsernameProblemLanguageResultExecution timeMemory
8447327modyOvertaking (IOI23_overtaking)C++17
Compilation error
0 ms0 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; struct item{ ll first,second,res; }; vector<pair<ll,ll>> arr; vector<vector<ll>> s; vector<vector<item>> a; vector<vector<item>> dp; vector<ll> station; vector<vector<item>> temp; ll n,x,m,mx; bool p(item a,item b){ if(a.first==b.first) return a.second > b.second; return a.first < b.first; } void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) { n=N;x=X;m=M; mx=L; dp.resize(m); for(int i=0; i < n;i++){ if(W[i] > x){ arr.push_back({W[i],(ll)T[i]}); } } temp.resize(m); 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()); // i love alwawi he is very smart. from SAAD reverse(arr.begin(),arr.end()); for(int i=0; i < m;i++){ s[i].resize(n); temp[i].resize(n); dp[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<item> curr(n); for(int j=0; j < n;j++){ curr[j]={s[i-1][j],s[i][j],j}; } sort(curr.begin(),curr.end(),p); a[i]=curr; } for(int i=0; i < n;i++){ dp[m-1][i]={T[i],s[m-1][i],s[m-1][i]}; temp[m-1][i]={s[m-2][i], s[m-1][i] , s[m-1][i]}; } sort(temp[m-1].begin(),temp[m-1].end(),p); sort(dp[m-1].begin(),dp[m-1].end(),p); for(int i=m-2; i >=1; i--){ for(int j=0; j < n;j++){ dp[i][j]={T[j],s[i][j],dp[i+1][j].res}; temp[i][j]={s[i-1][j],s[m-1][j],0}; int l=i+1,r=m-1; int ii=-1,jj=-1; while(l<=r){ int mid=(l+r)/2; int l1=0,r1=n-1; bool ok=false; ll length= station[mid] - station[i-1]; ll start = s[i-1][j]; ll expected = s[i-1][j] + (x * length); while(l1<=r1){ int mid1=(l1+r1)/2; if(start > temp[mid][mid1].first && temp[mid][mid1].second > expected){ ok=true; ii=mid; jj=mid1; r1=mid1-1; } else if (start > temp[mid][mid1].first){ l1=mid1-1; } else{ r1=mid1-1; } } if(ok) r= mid-1; else l=mid+1; } if(ii!=-1){ temp[i][j].res=temp[ii][jj].res; dp[i][j].res=temp[ii][jj].res; } else{ ll finish=s[i][j] + ((station[m-1] - station[i]) *x); temp[i][j].res=dp[i][j].res=finish; } } sort(temp[i].begin(),temp[i].end(),p); sort(dp[i].begin(),dp[i].end(),p); } } long long arrival_time(long long Y) { int l=1,r=m-1; int i=-1,j=-1; while(l<=r){ int mid=(l+r)/2; int l1=0,r1=n-1; vector<item> curr=dp[mid]; ll length=station[mid]; ll expected = Y + (x*length); bool ok=false; while(l1 <= r1){ int mid1=(l1+r1)/2; if(Y > curr[mid1].first && expected <= curr[mid1].second){ i=mid,j=mid1; r1=mid1-1; ok=true; } else if ( curr[mid1].first > Y) r1=mid1-1; else l1=mid1+1; } if(ok) r=mid-1; else l=mid+1; } if(i==-1){ // cout << 1 << endl; return (Y + (x*mx)); } return dp[i][j].res; } 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; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccivfZbm.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccLOmkpp.o:overtaking.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status