QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#138504 | #366. Long Distance Coach | konstantys# | 0 | 7ms | 28496kb | C++14 | 8.2kb | 2023-08-11 20:43:56 | 2024-07-04 02:35:43 |
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<<"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%