QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#138518 | #366. Long Distance Coach | konstantys# | 0 | 4ms | 28492kb | C++14 | 8.2kb | 2023-08-11 20:59:31 | 2024-07-04 01:37:31 |
Judging History
answer
#include<iostream>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<set>
#define ll long long
#define f first
#define l 262144
#define s second
using namespace std;
bool czypod(ll x,ll y,ll a,ll b){
return (y-a*x<b);
}
bool czypod2(ll x1,ll y1,ll x2,ll y2,ll x3,ll y3){
cerr<<"Czy "<<x3<<" "<<y3<<" jest pod prosta laczaca ("<<x1<<","<<y1<<") oraz ("<<x2<<","<<y2<<")?\n";
//a prostej to (y2-y1)/(x2-x1)
//chcę sprawdzić y3<b+a*x3
//y3<y1-a*x1+a*x3
//y3-y1<a(x3-x1)
//(y3-y1)(x2-x1)<(y2-y1)(x3-x1)
return (y3-y1)*(x2-x1)>(y2-y1)*(x3-x1);
}
ll x,w,t,a,b;
ll wyn;
int n,m;
int koniec;
vector<ll> rfl;
vector<pair<ll,ll>> pssngr;
ll il;
pair<ll,ll> narazie[200005];
int ktory[200005];
vector<int> v[200005];
int ojc[200005][15][2];
int dpth[200005];
ll lin[200005][2];
ll lin2[200005][2];
bool czylepszy(ll a,int i,int u){
if(i==-1) return 0;
if(u==-1) return 1;
return (lin2[i][0]*a-lin2[i][1])<(lin2[u][0]*a-lin2[u][1]);
}
bool czypod2(int c,int a,int b){
ll x1=lin2[c][0];
ll y1=lin2[c][1];
ll x2=lin2[a][0];
ll y2=lin2[a][1];
ll x3=lin2[b][0];
ll y3=lin2[b][1];
// cerr<<"Czy "<<x3<<" "<<y3<<" jest pod prosta laczaca ("<<x1<<","<<y1<<") oraz ("<<x2<<","<<y2<<")?\n";
//a prostej to (y2-y1)/(x2-x1)
//chcę sprawdzić y3<b+a*x3
//y3<y1-a*x1+a*x3
//y3-y1<a(x3-x1)
//(y3-y1)(x2-x1)<(y2-y1)(x3-x1)
return (y3-y1)*(x2-x1)>(y2-y1)*(x3-x1);
}
/*
int trisearch(int x,ll a){
int y=1;
for(int i=12;i>=1;i--){
if(dpth[ojc[x][i][1]]>=dpth[y]){
if(czylepszy(ojc[x][i-1][1],ojc[ojc[x][i-1][1]][i-1][1]) x=ojc[ojc[x][i-1][1]][i-1][1]; else y=ojc[x][i-1][1];
}
if(dpth[ojc[x][i][0]]>=dpth[y]){
if(czylepszy(ojc[x][i-1][0],ojc[x][i-1][1])) x=ojc[x][i-1][1]; else y=ojc[x][i-1][0];
}
}
int bst=x;
ll bsc=(lin[x][0]*a-lin[x][1]);
while(x!=y){
x=ojc[x][0][0];
if(lin[x][0]*a-lin[x][1])
}
}
// */
vector<int> dp[2*l+5];
void merge(int x){
dp[x]=dp[x<<1];
int s=dp[x].size();
for(auto u:dp[(x<<1)^1]){
while(s>=2)
if(czypod2(u,dp[x][s-2],dp[x][s-1])){
s--;
dp[x].pop_back();
}else break;
dp[x].emplace_back(u);
s++;
}
/* if(dp[x<<1].size()>0 && dp[(x<<1)^1].size()>0){
for(auto u:dp[x]) cerr<<u<<", ";
cerr<<"\n";
}*/
}
int trisearch(int x,ll a){
if(dp[x].size()==0) return -1;
int p=0,k=dp[x].size()-1,s1,s2,y=-1;
while(k>=p){
s1=(2*p+k)/3;
s2=(2*k+p+1)/3;
if(4*x-l==4) cerr<<p<<" "<<k<<" "<<s1<<" "<<s2<<"\n";
if(czylepszy(a,dp[x][s1],dp[x][s2])){
if(czylepszy(a,dp[x][s1],y)) y=dp[x][s1];
k=s2-1;
}else{
if(czylepszy(a,dp[x][s2],y)) y=dp[x][s2];
p=s1+1;
}
// cerr<<y<<" to y\n";
}
if(x*4-l==4){
cerr<<"wyszlo "<<a<<" "<<y<<", "<<dp[x].size()<<"\n";
for(auto u:dp[x]){
cerr<<u<<", ";
cerr<<lin2[u][0]<<" "<<lin2[u][1]<<"\n";
}
}
//if(x==3+l) cerr<<"wyszlo "<<y<<"\n";
return y;
}
int maksprzedzial(int x,int y,ll a){
int naj=x;
x--;
y++;
x+=l;
y+=l;
int pom;
while(true){
if(x==y) break;
if(x+1==y) break;
if(!(x&1)){
pom=trisearch(x^1,a);
//if(pom==1 || pom==2) cerr<<pom<<"\n";
//if(pom==0) cerr<<x<<" Kurza stopa!\n";
if(czylepszy(a,pom,naj)) naj=pom;
}
x>>=1;
if((y&1)){
pom=trisearch(y^1,a);
//if(y>l) cerr<<(y^1)-l<<" to y, udalo sie "<<pom<<"\n";
//if(y>l/2 && (2*y)-l==6) cerr<<pom<<" :3\n";
// if(pom==1 || pom==2) cerr<<pom<<"\n";
// if(naj!=0 && pom==0) cerr<<"Kurza stopa!\n";
if(czylepszy(a,pom,naj)) naj=pom;
}
//cerr<<naj<<" na razie najlepszy \n";
y>>=1;
}
return naj;
}
set<int> nextone;
bool czywziety[200005];
vector<ll> rfl2;
int main(){
//ios_base::sync_with_stdio(0);
scanf("%lld%d%d%lld%lld",&x,&n,&m,&w,&t);
for(int i=0;i<n;i++){
scanf("%lld",&a);
rfl.push_back(a);
}
wyn=x/t+1;
for(int i=0;i<m;i++){
scanf("%lld%lld",&a,&b);
if(a%t>x%t) b+=w;
wyn+=(x-a)/t+1;
pssngr.emplace_back(make_pair(a,b));
}
// cerr<<wyn<<" pić\n";
wyn*=w;
//tych co sa po koncu: refund jest tanszy i mniej dod do wyn
int p=0,k=m-1,y=0,s;
ll pom=x%t;
while(k>=p){
s=(p+k)>>1;
if(pssngr[s].first<pom){
y=s+1;
p=s+1;
}else k=s-1;
}
koniec=y;
n++;
rfl.push_back(x);
sort(rfl.begin(),rfl.end());
sort(pssngr.begin(),pssngr.end());
for(int i=0;i<n;i++){
p=0,k=m-1,y=0;
pom=rfl[i]%t;
//if(rfl[i]==x) pom=t;
while(k>=p){
s=(p+k)>>1;
if(pssngr[s].first<pom){
y=s+1;
p=s+1;
}else k=s-1;
}
rfl2.push_back(rfl[i]);
//cerr<<pom<<" "<<rfl[i]<<" "<<y<<" binsearch\n";
rfl[i]=y; //jest po y, przy czym pssngr jest zoffsetowane o 1
// cerr<<rfl[i]<<"\n";
}
//wszystko jest tak naprawdę mod pssngr.size()+1
ll t2=t;
t=pssngr.size()+1;
ll sum=0;
if(true){ //stare
/*il=0;
dpth[1]=1;
for(int i=1;i<t;i++){
//do wszystkich starych dodaję 1 oraz koszt refundu,
ll x=1,y=pssngr[i-1].second;
sum+=pssngr[i-1].second;
x-=i;
y-=sum;
lin[i][0]=i; //na ilu oszczedzam
lin[i][1]=pssngr[i-1].second; //ile trace
while(il>=2)
if(!czypod2(x,y,narazie[il-2].first,narazie[il-2].second,narazie[il-1].first,narazie[il-1].second)) il--; else break;
// cerr<<il<<"\n";
if(il>=1){
v[ktory[il-1]].push_back(i); //nie wiem czy bedzie potrzebne
ojc[i][0][0]=ktory[il-1];
ojc[i][0][1]=ojc[ktory[il-1]][0][0];
}
narazie[il]=make_pair(x,y);
ktory[il]=i;
dpth[i]=dpth[ktory[il-1]]+1;
il++;
}
for(int i=1;i<=12;i++){
for(int u=1;u<=t;u++){
ojc[u][i][0]=ojc[ojc[u][i-1][0]][i-1][1];
ojc[u][i][1]=ojc[ojc[u][i][0]][i][0];
}
}*/
}
for(int i=1;i<t;i++){
ll x=1,y=pssngr[i-1].second;
sum+=pssngr[i-1].second;
x-=i;
y-=sum;
lin2[i][0]=x;
lin2[i][1]=y;
dp[i+l].emplace_back(i);
lin[i][0]=i;
lin[i][1]=sum;
}
//cerr<<wyn<<"\n";
for(int i=l-1;i>=1;i--) merge(i);
for(int it7=0;it7<rfl.size();it7++){
auto i=rfl[it7];
auto u=rfl2[it7];
if(i==0){
cerr<<i<<" "<<u<<" nic \n";
continue;
}
if(czywziety[i]){
cerr<<i<<" moja robota tu jest zrobiona.\n";
continue;
}
set<int>::iterator it=nextone.lower_bound(i);
int pocz;
if(it==nextone.begin()) pocz=1; else{
it--;
pocz=*it;
pocz++;
}
cerr<<x<<" "<<u<<" "<<t2<<" "<<w*(1+(x/t2-u/t2))<<" tyle teraz\n";
cerr<<"Mogę na przedziale od "<<pocz<<" do "<<i<<"\n";
pocz=maksprzedzial(pocz,i,(1+(x-u)/t2)*w);
cerr<<"Zdecydowałem się na od "<<pocz<<" do "<<i<<"\n";
if(lin[i][1]-lin[pocz-1][1]>(lin[i][0]-lin[pocz-1][0])*w*(1+(x/t2-u/t2))){
cerr<<"Ale sie nie oplaca, bo ";
cerr<<"z refundow trace "<<lin[i][1]-lin[pocz-1][1]<<"\n";
cerr<<"A zaoszczedzam "<<(lin[i][0]-lin[pocz-1][0])*w*(1+(x/t2-u/t2))<<"\n";
continue;
}
wyn+=lin[i][1]-lin[pocz-1][1];
cerr<<"Z refundow trace "<<lin[i][1]-lin[pocz-1][1]<<"\n";
wyn-=(lin[i][0]-lin[pocz-1][0])*w*(1+(x/t2-u/t2));
cerr<<"Ale zaoszczedzam "<<(lin[i][0]-lin[pocz-1][0])*w*(1+(x/t2-u/t2))<<"\n";
nextone.insert(i);
for(int j=pocz;j<=i;j++) czywziety[j]=1;
}
printf("%lld",wyn);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 16
Accepted
time: 4ms
memory: 25072kb
input:
999999999999 1 1 1000000 4 1 2 3
output:
499999999999000003
result:
ok single line: '499999999999000003'
Test #2:
score: 0
Accepted
time: 0ms
memory: 28432kb
input:
5 1 1 15 4 2 3 4
output:
45
result:
ok single line: '45'
Test #3:
score: 0
Accepted
time: 4ms
memory: 25984kb
input:
5 1 1 15 4 3 2 13
output:
43
result:
ok single line: '43'
Test #4:
score: 0
Accepted
time: 4ms
memory: 24904kb
input:
5 1 1 15 4 3 2 19
output:
45
result:
ok single line: '45'
Test #5:
score: -16
Wrong Answer
time: 4ms
memory: 28492kb
input:
142 4 7 10 13 67 44 86 141 3 1000000000 6 1000000000 9 1000000000 1 60 4 81 7 48 10 14
output:
880
result:
wrong answer 1st lines differ - expected: '878', found: '880'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%