Submission #258179

#	Time	Username	Problem	Language	Result	Execution time	Memory
258179		Mercenary	Long Distance Coach (JOI17_coach)	C++14	100 / 100	177 ms	16492 KiB

coach

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <pair<ll,int>,null_type,less<pair<ll,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e5 + 5;
const int logn = log2(maxn) + 1;

struct point{
    ll a , b;
    point(ll a = 0 , ll b = 0):a(a),b(b){};
    bool operator < (const point other)const{
        if(a == other.a)return b < other.b;
        return a < other.a;
    }
    point operator + (const point other){
        return point(a + other.a , b + other.b);
    }
    point operator - (const point other){
        return point(a - other.a , b - other.b);
    }
    ll operator * (const point other){
        //turn right.
        return a * other.b - b * other.a;
    }
    ll valat(ll x){
        return a * x + b;
    }
};
int ccw(point a , point b , point c){
    return (a - b) * (c - b) >= 0;
}
void add(vector<point> & a , point b){
    while(a.size() >= 2 && ccw(b,a.back(),a[a.size() - 2]))a.pop_back();
    a.pb(b);
}
vector<point> s;
ll query(ll k){
    ll res = -2e18;
    int l = 0 , r = (int)s.size() - 1;
    while(l <= r){
        int mid = l + r >> 1;
        res = max(res , s[mid].valat(k));
        if(mid + 1 < s.size() && s[mid].valat(k) <= s[mid + 1].valat(k))l = mid + 1;
        else r = mid - 1;
    }
    res = max(res , s[l].valat(k));
    return res;
}
ll X , T , ST[maxn];
int m , n;
int W;
ll tmp[maxn];
pair<ll,int> a[maxn];
ll sum[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> X >> n >> m >> W >> T;
    for(int i = 1 ; i <= n ; ++i)cin >> ST[i];ST[++n] = X;
    for(int i = 1 ; i <= m ; ++i)cin >> a[i].first >> a[i].second;
    sort(a + 1 , a + m + 1);
    sort(ST + 1 , ST + n + 1 , greater<ll>());
    for(int i = 1 ; i <= m ; ++i)sum[i] = sum[i - 1] + a[i].second;
    for(int i = 1 ; i <= n ; ++i){
        tmp[lower_bound(a + 1 , a + m + 1 , mp(ST[i] % T , 0)) - a - 1] = ST[i];
    }
    add(s,point(0,0));
    ll res = 0;
    for(int i = 1 ; i <= m ; ++i){
        res += ((X - a[i].first) / T + 1) * W;
        if(tmp[i]){
            res = min(res , -query(tmp[i] / T * W) + tmp[i] / T * i * W + sum[i]);
        }
        add(s , point(i , sum[i] - res));
    }
    cout << res + (X / T + 1) * W;
}

Compilation message (stderr)

coach.cpp: In function 'll query(ll)':
coach.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
coach.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(mid + 1 < s.size() && s[mid].valat(k) <= s[mid + 1].valat(k))l = mid + 1;
            ~~~~~~~~^~~~~~~~~~
coach.cpp: In function 'int main()':
coach.cpp:76:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i = 1 ; i <= n ; ++i)cin >> ST[i];ST[++n] = X;
     ^~~
coach.cpp:76:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int i = 1 ; i <= n ; ++i)cin >> ST[i];ST[++n] = X;
                                               ^~
coach.cpp:72:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:73:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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