QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138518#366. Long Distance Coachkonstantys#0 4ms28492kbC++148.2kb2023-08-11 20:59:312024-07-04 01:37:31

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 01:37:31]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:28492kb
  • [2023-08-11 20:59:31]
  • 提交

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%