// High above the clouds there is a rainbow...
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
#define real STH_STRANGE
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
const int maxn=2e5+10,mod=1e9+7, SQ1=1, SQ2=(maxn/SQ1) + 5;
const ll inf=1e18;
ll a[maxn], d[maxn], dp[maxn], W, T;
pll p[maxn];
ll upd[maxn];
vector<pair<pll,int> > cht[SQ2], vv;
ll lz1[SQ2], lz2[SQ2];// tedad jaam // tedad prefix jaam
bool bad(pll a,pll b,pll c){
return ld(a.S-b.S) / ld(b.F-a.F) >= ld(b.S-c.S) / ld(c.F-b.F);
}
ll gety(pll p,ll x){
return p.F*x + p.S;
}
void add(vector< pair<pll,int> >&v, ll a,ll b,int i){
if(sz(v) && v.back().F.F == a){
if( v.back().F.S <= b ) return;
v.pop_back();
}
while(sz(v)>1 && bad(v[sz(v)-2].F, v[sz(v)-1].F, {a,b} ) ) v.pop_back();
v.PB({{a,b},i});
}
ll ask(vector<pair<pll,int> >&v, ll x){
assert(sz(v));
int l=0,r=sz(v);
while(r-l>2){
int mid=(l+r+1)>>1;
if(gety(v[mid-1].F,x) < gety(v[mid].F,x) ) r=mid;
else l=mid;
}
if(r-l==1) return gety(v[l].F,x);
return min( gety(v[l].F,x), gety(v[l+1].F,x) );
}
void relax(int id){
for(auto &x:cht[id])
x.F.S+= x.F.F * lz2[id] + lz1[id];
lz1[id]=lz2[id]=0;
vv=cht[id], cht[id].clear();
}
void build(int id){
for(auto x:vv)
add(cht[id], x.F.F, x.F.S, x.S);
}
void add(int f,int s,ll x){
if(f>=s) return;
int id=f/SQ1;
relax(id);
for(int i=0;i<id;i++) lz1[i]+= x*(s-f);
for(int i=0;i<sz(vv);i++) vv[i].S+= x* max(int(0), s-max(f,vv[i].S + 1));
build(id), f=SQ1* (id+1);
if(f>=s) return;
id=s/SQ1;
relax(id);
int cnt=0;
for(int i=sz(vv)-1;i>=0;i--){
vv[i].F.S+= x*cnt;
cnt+= vv[i].S < s;
}
build(id), s=SQ1 * id;
if(f>=s) return;
f/=SQ1, s/=SQ1;
while(f<s) cnt+=SQ1, lz1[s-1]+=x* cnt, lz2[s-1]+=x, s--;
}
ll ask(){
ll ans=inf;
for(int i=0;i<SQ2;i++){
if(sz(cht[i])) ans=min(ans, ask(cht[i],lz2[i]) + lz1[i]);
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
ll x; int n,m;
#ifdef shayan
// srand(time(0));
x=1e12, n=2e5, m=2e5, W=513051, T=1010;
#else
cin>>x>>n>>m>>W>>T;
#endif
for(int i=0;i<n;i++){
#ifdef shayan
a[i]= 1ll* (rand()%999) * (rand()%1000000) + 1;
#else
cin>>a[i];
#endif
}
sort(a,a+n);
a[n++]=x;
ll ans=W*((x/T)+1);
p[0]={0,inf}, d[0]=0;
for(int i=1;i<=m;i++){
#ifdef shayan
p[i].F= rand(), p[i].S= rand();
#else
cin>>p[i].F>>p[i].S;
#endif
d[i]=p[i].F;
p[i].S-= W* (x/T), ans+= W* (x/T);
if( (p[i].F%T) < (x%T) ) p[i].S-= W, ans+=W;
}
m++;
sort(p,p+m), sort(d,d+m);
for(int i=0;i<=m;i++){
upd[i]=inf;
}
ll lst=0;
for(int i=0;i<n;i++){
int A=lower_bound(d,d+m,lst %T)-d, B=lower_bound(d,d+m,a[i] %T)-d;
if( lst< (a[i]/T)*T ) A=0;
if(A!=B) upd[B]= min(upd[B], a[i]/T );
lst=a[i];
}
add(cht[0], -1, 0, 0);
vector< pair<pii,ll> >v;
int pt=0;
for(int i=1;i<=m;i++){
if(upd[i]!=inf){
if(sz(v)==0){
v.PB({{0,i},upd[i]});
}
else{
while(sz(v) && upd[i]<v.back().S) add(v.back().F.F, v.back().F.S, W*( upd[i]- v.back().S) ), v.pop_back();
v.PB({ {v.back().F.S,i}, upd[i]});
}
}
dp[i]=dp[i-1];
if(sz(v) && v.back().F.S==i) dp[i]= ask();
pt=max(pt,i+1);
while(pt<=m && upd[pt]==inf) pt++;
for(int j=0;j<SQ2;j++)
lz1[j]+= p[i].S + W* (pt<=m ? upd[pt] : 0);
int aa= -(i%SQ1)-1, id=i/SQ1;
add(cht[id], aa, dp[i]- aa*lz2[id] - lz1[id], i);
}
return cout<<dp[m]+ans<<endl,0;
}
// Deathly mistakes:
// * Read the problem curfully.
// * Check maxn
// * Overflows.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 5 |
Correct |
10 ms |
6644 KB |
Output is correct |
| 6 |
Correct |
12 ms |
6656 KB |
Output is correct |
| 7 |
Correct |
10 ms |
6656 KB |
Output is correct |
| 8 |
Incorrect |
10 ms |
6700 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 5 |
Correct |
10 ms |
6644 KB |
Output is correct |
| 6 |
Correct |
12 ms |
6656 KB |
Output is correct |
| 7 |
Correct |
10 ms |
6656 KB |
Output is correct |
| 8 |
Incorrect |
10 ms |
6700 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 5 |
Correct |
10 ms |
6644 KB |
Output is correct |
| 6 |
Correct |
12 ms |
6656 KB |
Output is correct |
| 7 |
Correct |
10 ms |
6656 KB |
Output is correct |
| 8 |
Incorrect |
10 ms |
6700 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6656 KB |
Output is correct |
| 5 |
Correct |
10 ms |
6644 KB |
Output is correct |
| 6 |
Correct |
12 ms |
6656 KB |
Output is correct |
| 7 |
Correct |
10 ms |
6656 KB |
Output is correct |
| 8 |
Incorrect |
10 ms |
6700 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
