oj.uz

답안 #122021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122021 2019-06-27T11:36:56 Z shayan_p Long Distance Coach (JOI17_coach) C++14
71 / 100
 206 ms 19596 KB 
// 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=55, SQ2=40;
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;
    while(f<s && s%SQ1) real[id][s-1- id*SQ1].S+= x*cnt, cnt++, s--;
    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.

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 428 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 3 ms 384 KB Output is correct
34 Correct 2 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 2 ms 384 KB Output is correct
37 Correct 2 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 428 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 3 ms 384 KB Output is correct
34 Correct 2 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 2 ms 384 KB Output is correct
37 Correct 2 ms 384 KB Output is correct
38 Correct 8 ms 512 KB Output is correct
39 Correct 11 ms 512 KB Output is correct
40 Correct 11 ms 640 KB Output is correct
41 Correct 9 ms 512 KB Output is correct
42 Correct 8 ms 512 KB Output is correct
43 Correct 8 ms 512 KB Output is correct
44 Correct 8 ms 512 KB Output is correct
45 Correct 8 ms 512 KB Output is correct
46 Correct 7 ms 640 KB Output is correct
47 Correct 11 ms 568 KB Output is correct
48 Correct 8 ms 512 KB Output is correct
49 Correct 6 ms 512 KB Output is correct
50 Correct 8 ms 512 KB Output is correct
51 Correct 8 ms 512 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 428 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 3 ms 384 KB Output is correct
34 Correct 2 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 2 ms 384 KB Output is correct
37 Correct 2 ms 384 KB Output is correct
38 Correct 8 ms 512 KB Output is correct
39 Correct 11 ms 512 KB Output is correct
40 Correct 11 ms 640 KB Output is correct
41 Correct 9 ms 512 KB Output is correct
42 Correct 8 ms 512 KB Output is correct
43 Correct 8 ms 512 KB Output is correct
44 Correct 8 ms 512 KB Output is correct
45 Correct 8 ms 512 KB Output is correct
46 Correct 7 ms 640 KB Output is correct
47 Correct 11 ms 568 KB Output is correct
48 Correct 8 ms 512 KB Output is correct
49 Correct 6 ms 512 KB Output is correct
50 Correct 8 ms 512 KB Output is correct
51 Correct 8 ms 512 KB Output is correct
52 Runtime error 206 ms 19596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Halted 0 ms 0 KB -