Submission #952416

#	Time	Username	Problem	Language	Result	Execution time	Memory
952416		idiotcomputer	Long Distance Coach (JOI17_coach)	C++11	100 / 100	233 ms	34428 KiB

coach

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pii pair<ll,ll>
#define f first 
#define s second 
#define pb push_back
#define sz size 

ll x,w,t;
int n,m;

const int mxN = 2e5+1;
ll points[mxN];
pii pass[mxN];

ll dp[mxN];
int idx[mxN];
int nextv[mxN];
ll psum[mxN];

struct cmp {
    bool operator() (int a, int b) const {
        return (points[idx[a]] > points[idx[b]]);
    }
};

ll qu(int a, int b){
    if (a < b) swap(a,b);
    ll v1 = dp[a];
    ll v2 = dp[b];
    if (nextv[a] > 0) v2 += psum[nextv[a]-1];
    if (nextv[b] > 0) v2 -= psum[nextv[b]-1];
    v2 += (nextv[a] - nextv[b]) * (points[idx[b]] / t) * w;
    if (points[idx[a]] > points[idx[b]]){
        swap(a,b);
        swap(v1,v2);
    }
    if (points[idx[b]]/t == points[idx[a]]/t){
        if (v1 > v2){
            return  (ll) 1 * 1e18;
        } else {
            return (ll) -1 * 1e18;
        }
    }
    return max(nextv[a],nextv[b]) - 1 + (int) ceil((double) (v1 - v2) / (double) ((points[idx[b]]/t - points[idx[a]]/t) * w));
}

int main()
{
    //psum[0] = 0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> x >> n >> m >> w >> t;
    n++;
    map<ll,ll> exist;
    ll a;
    int cnt = 0;
    for (int i =0; i < n; i++){
        if (i == n-1) a = x;
        else cin >> a;
        if (exist.find(a%t) == exist.end()){
         //   cout << a%t << " L\n";
            points[i-cnt] = a;
            exist[a%t] = i-cnt; 
        } else {
            cnt++;
            points[exist[a%t]] = min(points[exist[a%t]],a);
        }
    }
    n -= cnt;
    
    for (int i =0; i < m; i++) cin >> pass[i].f >> pass[i].s;
    
    vector<pii> all(n+m);
    for (int i = 0; i < n; i++) all[i] = {points[i] % t, i};
    for (int i = 0; i < m; i++) all[i+n] = {pass[i].f, i+n};
    
    sort(all.begin(),all.end());
    
   /* for (int i =0; i < n; i++){
        cout << points[i] << " ";
    }
    cout << '\n';
    for (int i =0; i < m; i++) cout << pass[i].f << "," << pass[i].s << " ";
    cout << '\n';*/
    ll alt;
    ll best = 0;
    cnt = 0;
    int cnt2 = 0;
    set<int,cmp> curr;
    for (int i =n+m-1; i >= 0; i--){
      //  cout << all[i].f << ',' << all[i].s << ": ";
        if (all[i].s < n){
           /* cout << " bef ";
            for (auto it = curr.begin(); it != curr.end(); it++){
                cout << (*it) << " ";
            }
            cout << '\n';*/
            idx[cnt2] = all[i].s;
            nextv[cnt2] = cnt;
            dp[cnt2] = best;
            auto it = curr.lower_bound(cnt2);
       
            if (it != curr.end()){
                auto it2 = it;
                it2++;
                while (it2 != curr.end() && qu(cnt2,(*it)) >= qu((*it),(*it2))){
                    curr.erase(it);
                    it = it2;
                    it2++;
                }
                it = curr.lower_bound(cnt2);
            }
            if (it != curr.begin()){
                it--;
                if (it != curr.begin()){
                    auto it2 = it;
                    it2--;
                    while (qu(cnt2,(*it)) <= qu((*it),(*it2))){
                        curr.erase(it);
                        it = it2;
                        if (it2 == curr.begin()){
                            break;
                        }
                        it2--;
                    }
                }
                it = curr.lower_bound(cnt2);
            }
            if (it != curr.end() && it != curr.begin()){
                auto it2 = it;
                it2--;
                if (qu(cnt2,*it) > qu(cnt2, *it2)){
                    curr.insert(cnt2);
                }
            } else {
                curr.insert(cnt2);
            }
            cnt2++;
         /*   cout << " aft ";
            for (auto it = curr.begin(); it != curr.end(); it++){
                cout << (*it) << " ";
            }
            cout << '\n';*/
        } else {
            all[i].s -= n;
            psum[cnt] = pass[all[i].s].s;
            if (cnt > 0) psum[cnt] += psum[cnt-1];
            while (curr.sz() > 1){
                auto it = curr.begin();
                auto it2 = it;
                it2++;
               // cout << (*it) << "-" << (*it2) << " " << qu((*it),(*it2)) << '\n';
                if (qu((*it),(*it2)) <= cnt){
                    curr.erase(it);
                } else {
                    break;
                }
            }
            
            ll alt = 1e18;
            if (curr.sz() > 0){
                int cidx = *(curr.begin());
                //cout << cidx << " C ";
                alt = dp[cidx] + psum[cnt];
                if (nextv[cidx] > 0) alt -= psum[nextv[cidx]-1];
                alt += (points[idx[cidx]] / t) * w * (cnt - nextv[cidx]+1);
            }
            ll ctimes = x / t;
            if (x%t > all[i].f){
                ctimes++;
            }
            best = min(best+ctimes*w,alt);
         //   cout << best << '\n';
            cnt++;
        }
      //  cout << '\n';
    }
    best += w * (x/t+1);
    cout << best << '\n';
    
    return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:88:8: warning: unused variable 'alt' [-Wunused-variable]
   88 |     ll alt;
      |        ^~~

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 29 / 29