| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1079673 | MarwenElarbi | 추월 (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "overtaking.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
const int nax=1e3+5;
long long timer[nax][nax];
long long segtree[nax][nax*4];
int n,m,x,e;
int tab[nax];
void update(int pos,int l,int r,int idx,int value,int i){
if(l==r){
segtree[i][pos]=value;
return;
}
int mid=(r+l)/2;
if(idx<=mid) update(pos*2+1,l,mid,idx,value,i);
else update(pos*2+2,mid+1,r,idx,value,i);
segtree[i][pos]=max(segtree[i][pos*2+1],segtree[i][pos*2+2]);
return;
}
long long query(int pos,int l,int r,int left,int right,int i){
if(l>r||l>right||r<left) return -1;
if(l>=left&&r<=right) return segtree[i][pos];
int mid=(r+l)/2;
return max(query(pos*2+1,l,mid,left,right,i),query(pos*2+2,mid+1,r,left,right,i));
}
int lower_bnd(int i,int x){
int l=-1;
int r=n;
while(r-l>1){
int mid=(r+l)/2;
if(timer[i][mid]<=x) l=mid;
else r=mid;
}
return l;
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
n=N,m=M,x=X,e=L;
vector<pair<long long,long long>> lst;
for (int i = 0; i < m; ++i) tab[i]=S[i];
for (int i = 0; i < n; ++i) lst.pb({T[i],W[i]});
for (int i = 0; i < m-1; ++i)
{
sort(lst.begin(),lst.end());
for (int j = 0; j < n; ++j) timer[i][j]=lst[j].fi;
priority_queue<int,vector<int>,greater<int>> pq;
lst.clear();
for (int j = 0; j < n; ++j)
{
long long cur=max(lst[j].se*1ll*(S[i+1]-S[i])+lst[j].fi,1ll*(!pq.empty() ? pq.top() : -1));
update(0,0,n-1,j,cur,i);
lst.pb({cur,lst[j].se});
}
}
return;
}
long long arrival_timer(long long Y)
{
for (int i = 0; i < m-1; ++i)
{
int cur=lower_bnd(i,Y-1);
long long cnt=Y+x*(tab[i+1]-tab[i]);
long long a=query(0,0,n-1,0,cur,i);
Y=max(cnt,a);
}
return Y;
}