QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138504#366. Long Distance Coachkonstantys#0 7ms28496kbC++148.2kb2023-08-11 20:43:562024-07-04 02:35:43

Judging History

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

  • [2024-07-04 02:35:43]
  • 评测
  • 测评结果:0
  • 用时:7ms
  • 内存:28496kb
  • [2023-08-11 20:43:56]
  • 提交

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<<"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<<i<<" 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: 0ms
memory: 25184kb

input:

999999999999 1 1 1000000 4
1
2 3

output:

499999999999000003

result:

ok single line: '499999999999000003'

Test #2:

score: 0
Accepted
time: 3ms
memory: 25780kb

input:

5 1 1 15 4
2
3 4

output:

45

result:

ok single line: '45'

Test #3:

score: 0
Accepted
time: 0ms
memory: 26664kb

input:

5 1 1 15 4
3
2 13

output:

43

result:

ok single line: '43'

Test #4:

score: 0
Accepted
time: 3ms
memory: 24908kb

input:

5 1 1 15 4
3
2 19

output:

45

result:

ok single line: '45'

Test #5:

score: 0
Accepted
time: 3ms
memory: 25260kb

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:

878

result:

ok single line: '878'

Test #6:

score: 0
Accepted
time: 5ms
memory: 26076kb

input:

142 3 8 10 13
68
46
37
4 1000000000
8 1000000000
1 61
2 59
5 79
6 79
9 20
10 155

output:

982

result:

ok single line: '982'

Test #7:

score: 0
Accepted
time: 5ms
memory: 25388kb

input:

150 8 8 10 18
5
88
75
87
83
14
109
112
17 30
7 70
2 24
10 25
12 34
9 92
8 30
13 18

output:

463

result:

ok single line: '463'

Test #8:

score: 0
Accepted
time: 5ms
memory: 25200kb

input:

10000000000 8 8 6 18
9547257284
4226673527
9454195771
9513946487
7287482436
6692534804
3951479147
8774939403
12 415893810
4 735304001
13 184845346
14 354080601
15 455062532
16 886416267
3 985580216
1 97417991

output:

18443869092

result:

ok single line: '18443869092'

Test #9:

score: 0
Accepted
time: 5ms
memory: 26624kb

input:

200 4 8 5 14
136
180
37
58
13 39
8 100
3 33
11 32
6 62
5 1
7 98
1 32

output:

601

result:

ok single line: '601'

Test #10:

score: 0
Accepted
time: 2ms
memory: 25032kb

input:

200 8 8 5 18
73
40
168
152
10
12
122
178
3 46
5 30
7 18
9 40
11 24
13 12
15 17
17 9

output:

370

result:

ok single line: '370'

Test #11:

score: 0
Accepted
time: 2ms
memory: 26028kb

input:

99999999999 7 7 3 16
75171012465
68638795379
63875989701
83563043959
64144786889
89597405323
74981605181
2 105022615
4 341401908
6 209850215
8 507409549
10 849182839
12 760157370
14 257217651

output:

116398917650

result:

ok single line: '116398917650'

Test #12:

score: 0
Accepted
time: 3ms
memory: 25472kb

input:

150 8 8 10 18
146
49
17
101
117
134
131
33
1 1
3 1
7 5215
12 2283658
4 69
14 23058601
16 170888234
10 148221

output:

751

result:

ok single line: '751'

Test #13:

score: 0
Accepted
time: 3ms
memory: 28496kb

input:

8001 7 8 6 17
3613
4410
5581
2885
1918
934
6395
10 131687242
13 284628020
2 541922
15 554928957
4 4115226
6 17341529
1 16935
8 52922149

output:

25422

result:

ok single line: '25422'

Test #14:

score: 0
Accepted
time: 0ms
memory: 25384kb

input:

250 8 8 10 18
238
189
86
221
120
173
53
205
6 300728
13 24836451
8 2800753
15 946925513
2 293
10 17341529
1 251803956
3 16935

output:

1260

result:

ok single line: '1260'

Test #15:

score: 0
Accepted
time: 5ms
memory: 28436kb

input:

1234567 8 8 1000000 18
2
22
42
62
82
102
122
142
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1

output:

137203000007

result:

ok single line: '137203000007'

Test #16:

score: 0
Accepted
time: 0ms
memory: 28412kb

input:

1234567 8 8 999 18
449660
490828
187404
376334
697798
1177644
1056704
312928
3 996683357
5 928740029
7 950657139
9 904761397
11 923725553
13 962648669
15 971692610
17 965766352

output:

616666716

result:

ok single line: '616666716'

Test #17:

score: 0
Accepted
time: 7ms
memory: 25600kb

input:

200 8 8 12 18
131
170
55
60
47
28
158
192
13 40
16 87
17 69
4 55
7 99
9 975663280
15 17
3 912112332

output:

1159

result:

ok single line: '1159'

Test #18:

score: 0
Accepted
time: 2ms
memory: 26516kb

input:

600 8 8 63 18
340
333
326
328
331
339
332
337
5 17
3 12
11 26
14 18
12 943485371
17 25
10 954990891
1 48

output:

15089

result:

ok single line: '15089'

Test #19:

score: 0
Accepted
time: 3ms
memory: 24808kb

input:

300 8 8 11 18
135
256
73
167
222
223
206
46
3 22
11 9
15 54
17 47
16 10
13 34
14 54
2 55

output:

1373

result:

ok single line: '1373'

Test #20:

score: 0
Accepted
time: 0ms
memory: 26116kb

input:

300 8 8 11 18
109
113
205
26
208
290
168
189
11 6
13 43
15 21
3 60
17 11
14 69
16 50
4 61

output:

1392

result:

ok single line: '1392'

Test #21:

score: -16
Wrong Answer
time: 0ms
memory: 26516kb

input:

300 8 8 11 18
205
201
265
59
261
268
251
186
14 38
2 17
10 60
1 76
11 6
8 11
15 44
4 42

output:

1290

result:

wrong answer 1st lines differ - expected: '1285', found: '1290'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%