Submission #1162360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162360		yeediot	Tower (JOI24_tower)	C++20	100 / 100	229 ms	16712 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void CHECK();
void setio(){
    freopen("/Users/iantsai/cpp/input.txt","r",stdin);
    freopen("/Users/iantsai/cpp/output.txt","w",stdout);
}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
#define TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
const int inf = 1e18;
void solve(){
    int n, q, d, a, b;
    cin >> n >> q >> d >> a >> b;
    vector<int>l(n + 1), r(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> l[i] >> r[i];
    }
    vector<pii>qry; 
    qry.pb({0, l[1] - 1});
    for(int i = 1; i < n; i++){
        if(r[i] + 1 <= l[i + 1] - 1) qry.pb({r[i] + 1, l[i + 1] - 1});
    }
    qry.pb({r[n] + 1, 1e18});
    vector<array<int, 3>>ans;
    ans.pb({qry[0].F, qry[0].S, 0});
    int pos = 0;
    for(int i = 1; i < sz(qry); i++){
        while(pos < sz(ans) and ans[pos][1] + d < qry[i].F){
            pos++;
        }
        if(pos < sz(ans) and ans[pos][0] + d <= qry[i].S){
            ans.pb({max(ans[pos][0] + d, qry[i].F), qry[i].S, ans[pos][2] + 1});
        }
    }
    auto find = [&](int x){
        array<int, 3> v = {x + 1, 0, 0};
        auto it = lower_bound(all(ans), v) - ans.begin();
        return it - 1;
    };
    if(d * a <= b){
        //assert(0);
        while(q--){
            int x;
            cin >> x;
            int it = find(x);
            if(it < 0 or ans[it][1] < x){
                cout << "-1\n";
            }
            else{
                cout << ans[it][2] * b + (x - ans[it][2] * d) * a << '\n';
            }
        }
    }
    else{
        vector<int>dp(sz(ans)), ad(sz(ans));
        auto cal = [&](int x){
            if(x < 0) return -1LL;
            int pos = find(x);
            if(x > ans[pos][1]){
                x = ans[pos][1];
            }
            assert(pos >= 0);
            int res = dp[pos] + (x - ans[pos][0]) / d + ((x - ans[pos][0]) % d > ad[pos]);
            return res;
        };
        debug(qry, ans);
        for(int i = 0; i < sz(ans); i++){
            if(ans[i][0] - d < 0){
                ad[i] = inf;
                continue;
            }
            int val = cal(ans[i][0] - d) + 1;
            int l = ans[i][0], r = min(ans[i][1], ans[i][0] + d - 1);
            while(l < r){
                int mm = l + r + 1 >> 1;
                if(cal(mm - d) + 1 > val){
                    r = mm - 1;
                }
                else{
                    l = mm;
                }
            }
            debug(l);
            dp[i] = val;
            ad[i] = l - ans[i][0];
        }
        debug(dp, ad);
        while(q--){
            int x;
            cin >> x;
            int p = find(x);
            if(p < 0 or ans[p][1] < x){
                cout << -1 << '\n';
                continue;
            }
            int v = cal(x);
            debug(x, v);
            cout << v * b + (x - v * d) * a << '\n';
        }
    }
}
signed main(){
    TOI_is_so_de;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef local
    CHECK();
    #endif
}
/*
input:
 
*/
#ifdef local
void CHECK(){
    cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    function<bool(string,string)> compareFiles = [](string p1, string p2)->bool {
        std::ifstream file1(p1);
        std::ifstream file2(p2);
        if(!file1.is_open() || !file2.is_open()) return false;
        std::string line1, line2;
        while (getline(file1, line1) && getline(file2, line2)) {
            if (line1 != line2)return false;
        }
        int cnta = 0, cntb = 0;
        while(getline(file1,line1))cnta++;
        while(getline(file2,line2))cntb++;
        return cntb - cnta <= 1;
    };
    bool check = compareFiles("output.txt","expected.txt");
    if(check) cerr<<"ACCEPTED\n";
    else cerr<<"WRONG ANSWER!\n";
}
#else
#endif

• Subtask 1: 5 / 5
• Subtask 2: 38 / 38
• Subtask 3: 25 / 25
• Subtask 4: 32 / 32