| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 27491 | 2017-07-13T07:48:34 Z | 서규호(#1154) | Long Distance Coach (JOI17_coach) | C++14 | 3 ms | 13156 KB |
#include <bits/stdc++.h>
#define lld long long
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007
using namespace std;
int N,M;
int it1[200002],it2[200002];
lld X,W,T,ans;
lld a[200002];
struct data{
lld d,c;
}b[200002];
bool check[200002];
queue<int> q;
vector<int> tmp[200002];
lld get(lld x){
return ((X-x)/T+1)*W;
}
bool flag;
void calc(int i){
int it;
lld small = 0,sum = 0;
for(int j=it2[i]; j>=it1[i]; j--){
if(check[j]) continue;
sum += b[j].c;
sum -= get((a[i]/T)*T+b[j].d);
if(small > sum){
small = sum;
it = j;
}
}
if(small == 0) return;
ans += small;
for(int j=it2[i]; j>=it; j--){
if(check[j]) continue;
q.push(j);
check[j] = true;
flag = true;
}
}
int main(){
//freopen("input.txt","r",stdin);
long long iX,iW,iT;
scanf("%lld %d %d %lld %lld",&iX,&N,&M,&iW,&iT);
X = iX; W = iW; T = iT;
for(int i=1; i<=N; i++){
long long ia;
scanf("%lld",&ia);
a[i] = ia;
}
sort(a+1,a+N+1);
ans += get(0);
for(int i=1; i<=M; i++){
long long id,ic;
scanf("%lld %lld",&id,&ic);
b[i].d = id; b[i].c = ic;
ans += get(b[i].d);
}
sort(b+1,b+M+1,[&](data &x,data &y){
return x.d < y.d;
});
a[N+1] = X;
for(int i=1; i<=N+1; i++){
lld s,e;
s = max(a[i-1],(a[i]/T)*T)+1;
e = a[i]-1;
if(s > e) continue;
s %= T; e %= T;
if(e < b[1].d || b[M].d < s) continue;
int l,r;
l = 1; r = M;
while(l <= r){
int m = (l+r)>>1;
if(b[m].d >= s){
it1[i] = m;
r = m-1;
}else l = m+1;
}
l = 1; r = M;
while(l <= r){
int m = (l+r)>>1;
if(b[m].d <= e){
it2[i] = m;
l = m+1;
}else r = m-1;
}
if(it1[i] > it2[i]) continue;
for(int j=it1[i]; j<=it2[i]; j++) tmp[j].pb(i);
calc(i);
flag = false;
while(!q.empty()){
int v = q.front();
q.pop();
for(auto &j : tmp[v]) calc(j);
}
if(flag) while(true);
}
for(int i=1; i<=N; i++) if(it1[i] <= it2[i] && it1[i]) calc(i);
if(!q.empty()) while(true);
long long print = ans;
printf("%lld\n",print);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 13156 KB | Output is correct |
| 2 | Correct | 0 ms | 13156 KB | Output is correct |
| 3 | Correct | 0 ms | 13156 KB | Output is correct |
| 4 | Correct | 0 ms | 13156 KB | Output is correct |
| 5 | Correct | 0 ms | 13156 KB | Output is correct |
| 6 | Correct | 0 ms | 13156 KB | Output is correct |
| 7 | Correct | 0 ms | 13156 KB | Output is correct |
| 8 | Correct | 0 ms | 13156 KB | Output is correct |
| 9 | Correct | 0 ms | 13156 KB | Output is correct |
| 10 | Correct | 0 ms | 13156 KB | Output is correct |
| 11 | Correct | 3 ms | 13156 KB | Output is correct |
| 12 | Correct | 0 ms | 13156 KB | Output is correct |
| 13 | Correct | 0 ms | 13156 KB | Output is correct |
| 14 | Correct | 3 ms | 13156 KB | Output is correct |
| 15 | Correct | 0 ms | 13156 KB | Output is correct |
| 16 | Correct | 0 ms | 13156 KB | Output is correct |
| 17 | Correct | 0 ms | 13156 KB | Output is correct |
| 18 | Correct | 3 ms | 13156 KB | Output is correct |
| 19 | Correct | 3 ms | 13156 KB | Output is correct |
| 20 | Correct | 3 ms | 13156 KB | Output is correct |
| 21 | Incorrect | 0 ms | 13156 KB | Output isn't correct |
| 22 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 13156 KB | Output is correct |
| 2 | Correct | 0 ms | 13156 KB | Output is correct |
| 3 | Correct | 0 ms | 13156 KB | Output is correct |
| 4 | Correct | 0 ms | 13156 KB | Output is correct |
| 5 | Correct | 0 ms | 13156 KB | Output is correct |
| 6 | Correct | 0 ms | 13156 KB | Output is correct |
| 7 | Correct | 0 ms | 13156 KB | Output is correct |
| 8 | Correct | 0 ms | 13156 KB | Output is correct |
| 9 | Correct | 0 ms | 13156 KB | Output is correct |
| 10 | Correct | 0 ms | 13156 KB | Output is correct |
| 11 | Correct | 3 ms | 13156 KB | Output is correct |
| 12 | Correct | 0 ms | 13156 KB | Output is correct |
| 13 | Correct | 0 ms | 13156 KB | Output is correct |
| 14 | Correct | 3 ms | 13156 KB | Output is correct |
| 15 | Correct | 0 ms | 13156 KB | Output is correct |
| 16 | Correct | 0 ms | 13156 KB | Output is correct |
| 17 | Correct | 0 ms | 13156 KB | Output is correct |
| 18 | Correct | 3 ms | 13156 KB | Output is correct |
| 19 | Correct | 3 ms | 13156 KB | Output is correct |
| 20 | Correct | 3 ms | 13156 KB | Output is correct |
| 21 | Incorrect | 0 ms | 13156 KB | Output isn't correct |
| 22 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 13156 KB | Output is correct |
| 2 | Correct | 0 ms | 13156 KB | Output is correct |
| 3 | Correct | 0 ms | 13156 KB | Output is correct |
| 4 | Correct | 0 ms | 13156 KB | Output is correct |
| 5 | Correct | 0 ms | 13156 KB | Output is correct |
| 6 | Correct | 0 ms | 13156 KB | Output is correct |
| 7 | Correct | 0 ms | 13156 KB | Output is correct |
| 8 | Correct | 0 ms | 13156 KB | Output is correct |
| 9 | Correct | 0 ms | 13156 KB | Output is correct |
| 10 | Correct | 0 ms | 13156 KB | Output is correct |
| 11 | Correct | 3 ms | 13156 KB | Output is correct |
| 12 | Correct | 0 ms | 13156 KB | Output is correct |
| 13 | Correct | 0 ms | 13156 KB | Output is correct |
| 14 | Correct | 3 ms | 13156 KB | Output is correct |
| 15 | Correct | 0 ms | 13156 KB | Output is correct |
| 16 | Correct | 0 ms | 13156 KB | Output is correct |
| 17 | Correct | 0 ms | 13156 KB | Output is correct |
| 18 | Correct | 3 ms | 13156 KB | Output is correct |
| 19 | Correct | 3 ms | 13156 KB | Output is correct |
| 20 | Correct | 3 ms | 13156 KB | Output is correct |
| 21 | Incorrect | 0 ms | 13156 KB | Output isn't correct |
| 22 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 13156 KB | Output is correct |
| 2 | Correct | 0 ms | 13156 KB | Output is correct |
| 3 | Correct | 0 ms | 13156 KB | Output is correct |
| 4 | Correct | 0 ms | 13156 KB | Output is correct |
| 5 | Correct | 0 ms | 13156 KB | Output is correct |
| 6 | Correct | 0 ms | 13156 KB | Output is correct |
| 7 | Correct | 0 ms | 13156 KB | Output is correct |
| 8 | Correct | 0 ms | 13156 KB | Output is correct |
| 9 | Correct | 0 ms | 13156 KB | Output is correct |
| 10 | Correct | 0 ms | 13156 KB | Output is correct |
| 11 | Correct | 3 ms | 13156 KB | Output is correct |
| 12 | Correct | 0 ms | 13156 KB | Output is correct |
| 13 | Correct | 0 ms | 13156 KB | Output is correct |
| 14 | Correct | 3 ms | 13156 KB | Output is correct |
| 15 | Correct | 0 ms | 13156 KB | Output is correct |
| 16 | Correct | 0 ms | 13156 KB | Output is correct |
| 17 | Correct | 0 ms | 13156 KB | Output is correct |
| 18 | Correct | 3 ms | 13156 KB | Output is correct |
| 19 | Correct | 3 ms | 13156 KB | Output is correct |
| 20 | Correct | 3 ms | 13156 KB | Output is correct |
| 21 | Incorrect | 0 ms | 13156 KB | Output isn't correct |
| 22 | Halted | 0 ms | 0 KB | - |