Submission #241442

#	Time	Username	Problem	Language	Result	Execution time	Memory
241442		osaaateiasavtnl	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2084 ms	24872 KiB

coach

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
 
const int N = 1e5+7;
struct SegTree {
 
int a[N];
void add(int l, int r, int x) {
    for (int i = l; i <= r; ++i)
        if (a[i] != -1)
            a[i] += x;
}
void ban(int l, int r) {
    for (int i = l; i <= r; ++i)
        a[i] = -1;        
}
int get(int l, int r) {
    int ans = -1;
    for (int i = l; i <= r; ++i)
        if (a[i] != -1)
            if (ans == -1 || ans > a[i])
                ans = a[i];
    return ans;
}   
 
} mag;
 
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int x, n, m, w, t;
    cin >> x >> n >> m >> w >> t;
 
    //first - d, second - c
 
    vector <int> s(n);
    for (int i = 0; i < n; ++i) 
        cin >> s[i];
    sort(all(s));
    s.app(x);
 
    vector <ii> a(m);
    for (int i = 0; i < m; ++i) 
        cin >> a[i].f >> a[i].s;
 
    sort(all(a));
    reverse(all(a));
    a.insert(a.begin(), mp(0, 0));
 
    map <int, int> pos;
    for (int i = 0; i < a.size(); ++i)
        pos[a[i].f] = i;        
 
    vector <int> c;
    for (auto e : a)    
        c.app(e.f);
    sort(all(c));
 
    vector <int> last(s.size()), mem(a.size(), s.size());
    for (int i = 0; i < s.size(); ++i) {
        int p = lower_bound(all(c), s[i]%t) - c.begin();
        p = (p - 1 + c.size()) % c.size();
        last[i] = pos[c[p]];
        mem[last[i]] = min(mem[last[i]], i);
    }
    vector <int> dp(a.size()+1);
    dp[0] = (x/t+1)*w;
    mag.add(0, 0, dp[0]);
    const int INF = 1e9;
    vector <ii> lf;
    for (int j = 1; j <= a.size(); ++j) {
        if (mem[j-1] != s.size()) {
            auto add = mp(mem[j-1], j-1);
            while (lf.size() && add < lf.back()) {
                lf.pop_back();
            }   
            lf.app(add);
        }
 
        int l = 0;
        for (auto e : lf) {
            int lf = e.f;
            mag.add(l, e.s-1, a[j-1].s);
            if (s[lf] > a[j-1].f) {
                mag.add(l, e.s-1, s[lf]/t*w);
            }
            l = e.s;
        }
        mag.ban(l, j - 2);
 
        int save = 0;
        if (j < a.size())
            save = (x/t+(a[j].f<=(x%t)))*w;
        int mn = mag.get(0, j - 1);
        if (mn != -1) {
            dp[j] = mn + save;
            mag.add(j, j, dp[j]);
        }
        else {
            dp[j] = -1;
            mag.ban(j, j);
        }
    }       
 
    cout << (int)dp[a.size()] << endl;
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i)
                     ~~^~~~~~~~~~
coach.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); ++i) {
                     ~~^~~~~~~~~~
coach.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 1; j <= a.size(); ++j) {
                     ~~^~~~~~~~~~~
coach.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (mem[j-1] != s.size()) {
coach.cpp:106:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (j < a.size())
             ~~^~~~~~~~~~
coach.cpp:83:15: warning: unused variable 'INF' [-Wunused-variable]
     const int INF = 1e9;
               ^~~

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