Submission #122004

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
122004	2019-06-27T11:00:54 Z	shayan_p	Long Distance Coach (JOI17_coach)	C++14	46 / 100	2000 ms	588 KB

coach

// 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=510, SQ2=400;
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>1){
	int mid=(l+r+1)>>1;
	if(gety(v[mid-1],x) < gety(v[mid],x) ) r=mid;
	else l=mid;
    }
    return gety(v[l],x);
}


void relax(int id){
    cht[id].clear();
    for(auto &x:real[id])
	x.S+= x.F * lz2[id] + lz1[id];    
}
void build(int id){
    for(auto &x:real[id])
	add(cht[id], x.F, x.S);
}
void add(int f,int s,ll x){
    int id=f/SQ1;
    relax(id);
    while(f<s && f%SQ1) real[id][f - id*SQ1].S+= x, f++;
    build(id);

    id=s/SQ1;
    relax(id);
    while(f<s && s%SQ1) real[id][s-1 - id*SQ1].S+= x, s--;
    build(id);
    
    if(f>=s) return;
    f/=SQ1, s/=SQ1;
    while(f<s) lz1[f]+=x, f++;   
}
void _add(int f,int s,ll x){
    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;
    int cnt=0;
    while(f<s && s%SQ1) real[id][s-1- id*SQ1].S+= x*cnt, cnt++;
    build(id);
    
    if(f>=s) return;
    f/=SQ1, s/=SQ1;
    while(f<s) cnt+=SQ1, lz1[f]+=x* cnt, lz2[f]+=x, f++;
}
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();
	
	add(0,i,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

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 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	3 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 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	3 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	4 ms	512 KB	Output is correct
24	Correct	3 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	4 ms	384 KB	Output is correct
28	Correct	4 ms	384 KB	Output is correct
29	Correct	3 ms	384 KB	Output is correct
30	Correct	3 ms	384 KB	Output is correct
31	Correct	3 ms	384 KB	Output is correct
32	Correct	3 ms	384 KB	Output is correct
33	Correct	4 ms	384 KB	Output is correct
34	Correct	3 ms	384 KB	Output is correct
35	Correct	3 ms	384 KB	Output is correct
36	Correct	3 ms	384 KB	Output is correct
37	Correct	3 ms	384 KB	Output is correct

Subtask #3
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 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	3 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	4 ms	512 KB	Output is correct
24	Correct	3 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	4 ms	384 KB	Output is correct
28	Correct	4 ms	384 KB	Output is correct
29	Correct	3 ms	384 KB	Output is correct
30	Correct	3 ms	384 KB	Output is correct
31	Correct	3 ms	384 KB	Output is correct
32	Correct	3 ms	384 KB	Output is correct
33	Correct	4 ms	384 KB	Output is correct
34	Correct	3 ms	384 KB	Output is correct
35	Correct	3 ms	384 KB	Output is correct
36	Correct	3 ms	384 KB	Output is correct
37	Correct	3 ms	384 KB	Output is correct
38	Execution timed out	2013 ms	588 KB	Time limit exceeded
39	Halted	0 ms	0 KB	-

Subtask #4
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 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	3 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	4 ms	512 KB	Output is correct
24	Correct	3 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	4 ms	384 KB	Output is correct
28	Correct	4 ms	384 KB	Output is correct
29	Correct	3 ms	384 KB	Output is correct
30	Correct	3 ms	384 KB	Output is correct
31	Correct	3 ms	384 KB	Output is correct
32	Correct	3 ms	384 KB	Output is correct
33	Correct	4 ms	384 KB	Output is correct
34	Correct	3 ms	384 KB	Output is correct
35	Correct	3 ms	384 KB	Output is correct
36	Correct	3 ms	384 KB	Output is correct
37	Correct	3 ms	384 KB	Output is correct
38	Execution timed out	2013 ms	588 KB	Time limit exceeded
39	Halted	0 ms	0 KB	-

Submission #122004

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 30.0 / 30.0

Subtask #3 0 / 25.0

Subtask #4 0 / 29.0

Subtask #1
16.0 / 16.0

Subtask #2
30.0 / 30.0

Subtask #3
0 / 25.0

Subtask #4
0 / 29.0