QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138463 | #366. Long Distance Coach | Rafi22# | 0 | 3ms | 31828kb | C++14 | 3.4kb | 2023-08-11 19:11:57 | 2024-07-04 01:37:07 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
__int128 inf=3000000000000000007;
int mod=1000000007;
int mod1=998244353;
const int N=200007,pot=1<<18;
map<int,vector<int>>M;
//vector<pair<int,int>>W[N];
__int128 W[N];
void add(int l,int r,__int128 c)
{
W[r]=min(W[r],c);
// W[r].pb({l,c});
}
__int128 DP[N];
__int128 P[2*pot+7];
__int128 best[2*pot+7];
__int128 lzy[2*pot+7];
__int128 sum[2*pot+7];
void push(int v,int s)
{
if(lzy[v]!=-1)
{
sum[2*v]=lzy[v]*s/2;
lzy[2*v]=lzy[v];
sum[2*v+1]=lzy[v]*s/2;
lzy[2*v+1]=lzy[v];
lzy[v]=-1;
}
}
void ins(int v,int a,int b,int l,int r,__int128 k)
{
if(a<=l&&b>=r)
{
lzy[v]=min(lzy[v],k);
sum[v]=(r-l+1)*k;
return ;
}
if(r<a||l>b) return ;
push(v,r-l+1);
ins(2*v,a,b,l,(l+r)/2,k);
ins(2*v+1,a,b,(l+r)/2+1,r,k);
best[v]=min(best[2*v]+sum[2*v+1],best[2*v+1]);
sum[v]=sum[2*v]+sum[2*v+1];
}
void upd(int v,int a,int l,int r,__int128 k)
{
if(l==r)
{
best[v]=k;
return ;
}
push(v,r-l+1);
if(a<=(l+r)/2) upd(2*v,a,l,(l+r)/2,k);
else upd(2*v+1,a,(l+r)/2+1,r,k);
best[v]=min(best[2*v]+sum[2*v+1],best[2*v+1]);
}
pair<__int128,__int128> que(int v,int a,int b,int l,int r)
{
if(a<=l&&b>=r) return {best[v],sum[v]};
if(r<a||l>b) return {inf,0};
push(v,r-l+1);
pair<__int128,__int128> L=que(2*v,a,b,l,(l+r)/2);
pair<__int128,__int128> R=que(2*v+1,a,b,(l+r)/2+1,r);
return {min(L.st+R.nd,R.st),L.nd+R.nd};
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int x,n,m,w,t;
cin>>x>>n>>m>>w>>t;
int ans=x/t+1;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
M[a/t].pb(a%t);
}
M[x/t].pb(x%t);
vector<pair<int,int>>C(m+1);
C[0].st=-inf;
for(int i=1;i<=m;i++)
{
cin>>C[i].st>>C[i].nd;
ans+=(x-C[i].st)/t+1;
}
ans*=w;
sort(all(C));
for(int i=1;i<=m+1;i++) W[i]=inf;
for(auto [p,y]:M)
{
vector<int>V=y;
sort(all(V));
int l=1;
for(auto i:V)
{
int r=--lower_bound(all(C),make_pair(i,0LL))-C.begin();
if(l<=r) add(l,r,p);
l=r+1;
}
}
for(int i=1;i<=pot;i++) sum[i+pot-1]=inf;
for(int i=pot-1;i>0;i--) sum[i]=sum[2*i]+sum[2*i+1];
for(int i=1;i<2*pot;i++)
{
best[i]=inf;
lzy[i]=-1;
}
for(int i=1;i<=m;i++)
{
P[i]=P[i-1]+C[i].nd-((x-C[i].st)/t+1)*w;
// cout<<(ll)P[i]<<" ";
}
// cout<<endl;
vector<pair<int,int>>Q;
Q.pb({-inf,0});
for(int i=1;i<=m+1;i++)
{
upd(1,i,1,pot,DP[i-1]-P[i-1]);
DP[i]=P[i-1]+que(1,1,i,1,pot).st;
if(W[i]!=inf)
{
while(Q.back().st>=W[i]) Q.pop_back();
ins(1,Q.back().nd+2,i+1,1,pot,W[i]*w);
// cout<<"COS "<<Q.back().nd+1<<" "<<i<<endl;
Q.pb({W[i],i});
}
// cout<<(ll)DP[i]<<" ";
}
// cout<<endl;
cout<<ans+(ll)DP[m+1]<<endl;
return 0;
}
/*
19 1 4 8 7
10
1 20
2 10
4 5
6 5
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 16
Accepted
time: 0ms
memory: 30348kb
input:
999999999999 1 1 1000000 4 1 2 3
output:
499999999999000003
result:
ok single line: '499999999999000003'
Test #2:
score: 0
Accepted
time: 0ms
memory: 31828kb
input:
5 1 1 15 4 2 3 4
output:
45
result:
ok single line: '45'
Test #3:
score: 0
Accepted
time: 0ms
memory: 30468kb
input:
5 1 1 15 4 3 2 13
output:
43
result:
ok single line: '43'
Test #4:
score: 0
Accepted
time: 0ms
memory: 31588kb
input:
5 1 1 15 4 3 2 19
output:
45
result:
ok single line: '45'
Test #5:
score: -16
Wrong Answer
time: 3ms
memory: 31068kb
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%