Submission #1140797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140797		pokmui9909	Tower (JOI24_tower)	C++17	0 / 100	2096 ms	61616 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second

const ll INF = 2e18;
ll N, Q, D, A, B, S, L[200005], R[200005], Ans[200005];

struct Event{
    ll li, ri, lx, rx, t;
    bool operator<(const Event &k) const{
        if(li != k.li) return li < k.li;
        return ((t < 0 || k.t < 0) ? t > k.t : lx < k.lx);
    }
};

struct Naive{
    ll T[2500005] = {};
    void upd(ll l, ll r, ll v){
        for(ll i = l; i <= r; i++){
            T[i] = min(T[i], v);
			if(i > l) T[i] = min(T[i], T[i - 1]);
        }
    }
    void No(ll l, ll r){
        for(ll i = l; i <= r; i++){
            T[i] = INF;
        }
    }
	ll Min(ll l, ll r){
		ll t = INF;
		for(ll i = l; i <= r; i++){
			t = min(t, T[i]);
		}
		return t;
	}
    ll qry(ll k){
        return T[k];
    }
}seg;

int main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> N >> Q >> D >> A >> B;
    vector<ll> Coord;
    for(ll i = 1; i <= N; i++){
        cin >> L[i] >> R[i];
    }
    R[0] = -1, L[N + 1] = 1e12 + 1;
    vector<Event> Ev;
    set<ll> chk;
    for(ll i = 1; i <= Q; i++){
        ll k; cin >> k;
        Ev.push_back({k / D, k / D, k % D, k % D, -i});
        Coord.push_back(k % D);
        chk.insert(k / D);
    }
	Coord.push_back(0);
    Coord.push_back(D - 1);
    for(ll i = 0; i <= N; i++){
        ll l = R[i] + 1, r = L[i + 1] - 1;
        Coord.push_back(l % D); Coord.push_back(r % D);
        if(l / D == r / D){
            Ev.push_back({l / D, l / D, l % D, r % D, 1});
        } else {
            Ev.push_back({l / D, l / D, l % D, D - 1, 1});
            Ev.push_back({r / D, r / D, 0, r % D, 1});
            if(r / D > l / D + 1){
                auto it = chk.lower_bound(l / D + 1);
                ll t = l / D + 1;
                while(it != chk.end()){
					if(*it >= r / D) break;
                    Ev.push_back({t, *it, 0, D - 1, 1});
                    t = *it + 1;
                    it = next(it);
                }
                if(t <= r / D - 1) Ev.push_back({t, r / D - 1, 0, D - 1, 1});
            }
        }
        
        if(i >= 1){
            l = L[i], r = R[i];
        	Coord.push_back(l % D); Coord.push_back(r % D);
            if(l / D == r / D){
                Ev.push_back({l / D, l / D, l % D, r % D, 0});
            } else {
                Ev.push_back({l / D, l / D, l % D, D - 1, 0});
                Ev.push_back({r / D, r / D, 0, r % D, 0});
				if(r / D > l / D + 1){
					auto it = chk.lower_bound(l / D + 1);
					ll t = l / D + 1;
					while(it != chk.end()){
						if(*it >= r / D) break;
						Ev.push_back({t, *it, 0, D - 1, 0});
						t = *it + 1;
						it = next(it);
					}
					if(t <= r / D - 1) Ev.push_back({t, r / D - 1, 0, D - 1, 0});
				}
            }
        }
    }
    sort(Ev.begin(), Ev.end());
    sort(Coord.begin(), Coord.end()); Coord.erase(unique(Coord.begin(), Coord.end()), Coord.end());
    for(auto &e : Ev){
        e.lx = lower_bound(Coord.begin(), Coord.end(), e.lx) - Coord.begin();
        e.rx = lower_bound(Coord.begin(), Coord.end(), e.rx) - Coord.begin();
    }
    S = Coord.size();
    ll Cur = -1;
	ll ok = 0;
    for(auto e : Ev){
        if(e.t == 0){
            seg.No(e.lx, e.rx);
        } else if(e.t == 1){
            if(e.li != e.ri){
				ll c = min((A * D - B) * (e.ri - e.li), A * D - B);
				if(e.ri > e.li && seg.Min(0, S - 1) != INF) seg.upd(0, S - 1, seg.Min(0, S - 1) + c);
                if(e.li != 0 && seg.qry(S - 1) != INF) seg.upd(0, S - 1, seg.qry(S - 1) + A * D - B);
                seg.upd(0, S - 1, seg.qry(0));
                Cur = e.ri;
            } else {
                if(e.lx == 0 & e.li != 0 && seg.qry(S - 1) != INF) seg.upd(e.lx, e.rx, seg.qry(S - 1) + A * D - B);
				seg.upd(e.lx, e.rx, seg.qry(e.lx));
                Cur = e.li;
            }
        } else {
            ll q = seg.qry(e.lx);
            Ans[-e.t] = (q >= INF ? -1 : q + A * Coord[e.lx] + B * e.li);
        }
    }
    for(ll i = 1; i <= Q; i++){
        cout << Ans[i] << '\n';
    }
}

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