oj.uz

Submission #600717

# Submission time Handle Problem Language Result Execution time Memory
600717 2022-07-21T07:25:59 Z 조영욱(#8469) Long Distance Coach (JOI17_coach) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;

long long x;
int n,m;
long long w,t;
vector<long long> s;
long long c1[200000];
typedef pair<long long,long long> P;
vector<P> vec;
long long mn[200001];
long long psum[200001];
long long dp[200001];
long long MX=1e12+7;

struct Node {
    P line;
    int l,r;
};

vector<Node> seg;
Node emp={P(0,3e18),-1,-1};

long long f(P line,long long x) {
    return line.first*x+line.second;
}

void insert(P line,int node=0,long long xl=0,long long xr=MX) {
    long long mid=(xl+xr)/2;
    P low=line;
    P high=seg[node].line;
    if (f(low,xl)>f(high,xr)) {
        swap(low,high);
    }
    if (f(low,xr)<=f(high,xr)) {
        seg[node].line=low;
        return;
    }
    if (f(low,mid)<=f(high,mid)) {
        seg[node].line=low;
        if (seg[node].r==-1) {
            seg[node].r=seg.size();
            seg.push_back(emp);
        }
        insert(high,seg[node].r,mid+1,xr);
    }
    else {
        seg[node].line=high;
        if (seg[node].l==-1) {
            seg[node].l=seg.size();
            seg.push_back(emp);
        }
        insert(low,seg[node].l,mid+1,xr);
    }
}

long long query(long long xq) {
    int node=0;
    long long xl=0;
    long long xr=MX;
    long long ret=3e18;
    while (node!=-1) {
        ret=min(ret,f(seg[node].line,xq));
        long long mid=(xl+xr)/2;
        if (xq<=mid) {
            xr=mid;
            node=seg[node].l;
        }
        else {
            xl=mid+1;
            node=seg[node].r;
        }
    }
    return ret;
}

int main() {
    scanf("%lld %d %d %lld %lld",&x,&n,&m,&w,&t);
    for(int i=0;i<n;i++) {
        long long val;
        scanf("%lld",&val);
        s.push_back(val);
    }
seg.push_back(emp);
    s.push_back(x);
    sort(s.begin(),s.end());
    for(int i=0;i<m;i++) {
        long long d;
        long long c;
        scanf("%lld %lld",&d,&c);
        vec.push_back(P(d,c));
    }
    vec.push_back(P(0,0));
    sort(vec.begin(),vec.end());
    for(int i=0;i<=m;i++) {
        mn[i]=-1;
    }
    for(int i=0;i<s.size();i++) {
        int ind=lower_bound(vec.begin(),vec.end(),P(s[i]%t,-1))-vec.begin()-1;
        if (mn[ind]==-1) {
            mn[ind]=s[i]/t;
        }
    }
    dp[0]=((x/t)+1)*w;
insert(P(0,dp[0]));
    for(int i=1;i<=m;i++) {
        psum[i]=psum[i-1]+vec[i].second;
        long long cnt=x/t+(vec[i].first<x%t);
        dp[i]=9e18;
        dp[i]=min(dp[i],dp[i-1]+cnt*w);
        if (mn[i]!=-1) {
                dp[i]=min(dp[i],query(mn[i])+psum[i]+w*mn[i]*i);
        }
        insert(P(-w*i,dp[i]-psum[i]));
        //printf(".%lld\n",dp[i]);
    }
    printf("%lld",dp[m]);
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i=0;i<s.size();i++) {
      |                 ~^~~~~~~~~
coach.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%lld %d %d %lld %lld",&x,&n,&m,&w,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%lld",&val);
      |         ~~~~~^~~~~~~~~~~~~
coach.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         scanf("%lld %lld",&d,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -