이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// 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=205, SQ2=1000;
const ll inf=1e18;
ll a[maxn], d[maxn], dp[maxn], W, T;
pll p[maxn];
pair<ll,int> upd[maxn];
vector<pll> cht[SQ2], real[SQ2];
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<pll>&v, ll a,ll b){
if(sz(v) && v.back().F == a){
if( v.back().S <= b ) return;
v.pop_back();
}
while(sz(v)>1 && bad(v[sz(v)-2], v[sz(v)-1], {a,b} ) ) v.pop_back();
v.PB({a,b});
}
ll ask(vector<pll>&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],x) < gety(v[mid],x) ) r=mid;
else l=mid;
}
if(r-l==1) return gety(v[l],x);
return min( gety(v[l],x), gety(v[l+1],x) );
}
void relax(int id){
cht[id].clear();
for(auto &x:real[id])
x.S+= x.F * lz2[id] + lz1[id];
lz1[id]=lz2[id]=0;
}
void build(int id){
for(auto x:real[id])
add(cht[id], x.F, 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(real[id]);i++) real[id][i].S+= x* max(int(0), s-max(f,i + id*SQ1 +1));
build(id), f=SQ1* (id+1);
id=s/SQ1;
relax(id);
int cnt=0, w=s%SQ1;
while(f<s && w) real[id][s-1- id*SQ1].S+= x*cnt, cnt++, s--, w--;
build(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; cin>>x>>n>>m>>W>>T;
for(int i=0;i<n;i++){
cin>>a[i];
}
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++){
cin>>p[i].F>>p[i].S;
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,0};
}
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,A} );
lst=a[i];
}
real[0].PB({-1,0});
build(0);
vector< pair<pii,ll> >v;
for(int i=1;i<=m;i++){
if(upd[i].F!=inf){
pair<ll,int>p=upd[i];
if(sz(v)==0){
assert(p.S==0);
add(0,i, W*p.F);
v.PB({{0,i},p.F});
}
else{
add(v.back().F.S, i, W* p.F);
while(sz(v) && p.F<v.back().S) add(v.back().F.F, v.back().F.S, W*( p.F- v.back().S) ), v.pop_back();
v.PB({ {v.back().F.S,i}, p.F});
}
}
dp[i]=dp[i-1];
if(sz(v) && v.back().F.S==i) dp[i]= ask();
for(int j=0;j<SQ2;j++)
lz1[j]+= p[i].S;
relax(i/SQ1);
real[i/SQ1].PB({-(i%SQ1)-1,dp[i]});
build(i/SQ1);
}
return cout<<dp[m]+ans<<endl,0;
}
// Deathly mistakes:
// * Read the problem curfully.
// * Check maxn
// * Overflows.
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |