Submission #414917

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414917	2021-05-31T10:37:13 Z	Pro_ktmr	코알라 (JOI13_koala)	C++17	Compilation error	0 ms	0 KB

koala

#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

#include <boost/multiprecision/cpp_int.hpp>
namespace boost_multiprecision = boost::multiprecision;
#define lll boost_multiprecision::cpp_int

const lll INF = 1'000'000'000'000'000'000LL;

template<typename T>
struct SegmentTree{
private:
    int N;
    vector<T> node;
    function<T(T, T)> F;
    T DEFAULT;
public:
    void init(int n, function<T(T, T)> f, T def){
        F = f;
        DEFAULT = def;
        N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, DEFAULT);
    }
    T& operator [](int a){
        return node[a+N-1];
    }
    void update(int a, T x){
        a += N-1;
        node[a] = x;
        while(a > 0){
            a = (a-1)>>1;
            node[a] = F(node[(a<<1)+1], node[(a<<1)+2]);
        }
    }
    void maximize(int a, T x){
        if(node[a+N-1] > x) return;
        update(a, x);
    }
    T query(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        if(b <= l || r <= a) return DEFAULT;
        if(a <= l && r <= b) return node[k];
        return F(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r));
    }
};

lll S, G, D, A;
int N;
lll T[100001], B[100001];

vector<lll> v;
SegmentTree<lll> st;

signed main(){
    cin >> S >> G >> D >> A >> N;
    rep(i, N) cin >> T[i] >> B[i];
    T[N] = G; B[N] = 0;

    v.pb(S%D); v.pb(G%D);
    rep(i, N) v.pb(T[i]%D);
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    st.init(v.size(), [](lll a, lll b){ return max(a, b); }, -INF*INF);

    st.maximize(lower_bound(all(v), S%D)-v.begin(),
        (lll)D*(INF+0) + (lll)A*S - (lll)A*(S%D));
    rep(i, N+1){
        int idx = lower_bound(all(v), T[i]%D)- v.begin();
        lll tmp1 = (st.query(0, idx) - (lll)A*(D-T[i]%D) - (lll)A*T[i] + D-1) / D + B[i];
        lll tmp2 = (st.query(idx, v.size()) + (lll)A*(T[i]%D) - (lll)A*T[i] + D-1) / D + B[i];
        st.maximize(idx, (lll)D*max(tmp1,tmp2) + (lll)A*T[i] - (lll)A*(T[i]%D));
        if(i == N) cout << max(tmp1, tmp2) - INF << endl;
    }
}

Compilation message

koala.cpp:15:10: fatal error: boost/multiprecision/cpp_int.hpp: No such file or directory
   15 | #include <boost/multiprecision/cpp_int.hpp>
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.