Submission #24922

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24922	2017-06-17T07:40:13 Z	tlwpdus	코알라 (JOI13_koala)	C	Compilation error	0 ms	0 KB

koala

    #include <bits/stdc++.h>
     
    using namespace std;
     
    typedef long long ll;
     
    ll tree[530000], d, a, n;
    ll b[100100], t[100100];
    int key = 262144;
     
    void upd(int s, int e, ll val) {
        s+=key;e+=key;
        while(s<=e) {
            if (s%2==1) tree[s] = max(tree[s],val);
            if (e%2==0) tree[e] = max(tree[e],val);
            s = (s+1)>>1; e = (e-1)>>1;
        }
    }
     
    ll getv(int idx) {
        ll maxi = -(1LL<<50);
        idx+=key;
        while(idx>0) {
            maxi = max(maxi,tree[idx]);
            idx>>=1;
        }
        return maxi;
    }
     
    vector<ll> comp;
    void com(ll t[]) {
        int i;
        for (i=0;i<n;i++) {
            comp.push_back(t[i]%d);
            comp.push_back((t[i]+1)%d);
        }
        comp.push_back(d);
        sort(comp.begin(),comp.end());
        comp.erase(unique(comp.begin(),comp.end()),comp.end());
    }
     
    ll mokx(ll a, ll b) {
        if (a>0) return (a-1)/b+1;
        return a/b;
    }
     
    int loc(ll val) {
        return lower_bound(comp.begin(),comp.end(),val)-comp.begin();
    }
     
    ll f[100100];
    void solve() {
        int i;
        upd(loc(0),loc(0),0);
        upd(loc(1),loc(d),-a);
        for (i=1;i<n;i++) {
            f[i] = getv(loc(t[i]%d))-(t[i]/d)*a+b[i];
            upd(loc(0),loc(t[i]%d),-(mokx(-t[i],d)*a)+f[i]);
            upd(loc((t[i]+1)%d),loc(d),-(mokx(d-t[i],d)*a)+f[i]);
        }
        printf("%lld\n",f[n-1]);
    }
     
    int main() {
        ll kt, mt;
        int i;
     
        for (i=1;i<key*2;i++) tree[i] = -(1LL<<50);
        scanf("%lld%lld%lld%lld%lld",&kt,&mt,&d,&a,&n);
        t[0] = 0; t[n+1] = mt-kt;
        for (i=1;i<=n;i++) {
            scanf("%lld%lld",&t[i],&b[i]);
            t[i]-=kt;
        }
        n+=2;
        com(t);
        solve();
     
        return 0;
    }

Compilation message

koala.c:1:29: fatal error: bits/stdc++.h: No such file or directory
     #include <bits/stdc++.h>
                             ^
compilation terminated.