Submission #1140872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140872		pokmui9909	Tower (JOI24_tower)	C++17	63 / 100	1577 ms	127216 KiB

Main

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

#define x first
#define y second

const ll INF = 5e18, MAX_ANS = 1e18;
ll N, Q, D, A, B, S, L[5000005], R[5000005], Ans[5000005];
set<ll> Mx;

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 SegTree{
	ll T[5000005], Rval[5000005], Lz[5000005];
	void upd(ll l, ll r, ll v) { upd(1, 1, S, l + 1, r + 1, v); }
	ll Go(ll l, ll r, ll v) { return Go(1, 1, S, l + 1, r + 1, v); }
	ll qry(ll l, ll r) { return qry(1, 1, S, l + 1, r + 1); }

	void prop(ll n, ll s, ll e){
		if(Lz[n] == 9e18) return;
		if(s != e){
			Lz[n * 2] = Lz[n * 2 + 1] = Lz[n];
		}
		T[n] = Rval[n] = Lz[n], Lz[n] = 9e18;
	}
	void upd(ll n, ll s, ll e, ll l, ll r, ll v){
		prop(n, s, e);
		if(e < l || s > r) return;
		if(l <= s && e <= r){
			Lz[n] = v; prop(n, s, e); return;
		}
		ll m = (s + e) / 2;
		upd(n * 2, s, m, l, r, v); upd(n * 2 + 1, m + 1, e, l, r, v);
		T[n] = min(T[n * 2], T[n * 2 + 1]);
		Rval[n] = Rval[n * 2 + 1];
	}
	ll Go(ll n, ll s, ll e, ll l, ll r, ll v){
		prop(n, s, e);
		if(s == e){
			return (T[n] >= v && l <= s && s <= r ? s - 1 : -1);
		}
		ll m = (s + e) / 2;
		if(r <= m) return Go(n * 2, s, m, l, r, v);
		if(l > m) return Go(n * 2 + 1, m + 1, e, l, r, v);
		prop(n * 2, s, m);
		if(Rval[n * 2] >= v){
			ll f = Go(n * 2 + 1, m + 1, e, l, r, v);
			return (f == -1 ? m - 1: f);
		}
		return Go(n * 2, s, m, l, r, v);
	}
	ll qry(ll n, ll s, ll e, ll l, ll r){
		prop(n, s, e);
		if(e < l || s > r) return INF;
		if(l <= s && e <= r) return T[n];
		ll m = (s + e) / 2;
		return min(qry(n * 2, s, m, l, r), qry(n * 2 + 1, m + 1, e, l, r));
	}
}seg;

void Chmin(ll l, ll r, ll v){
	vector<ll> V;
	Mx.insert(l);
	auto it = Mx.lower_bound(l);
	while(it != Mx.end()){
		if(*it > r) break;
		V.push_back(*it);
		it = Mx.erase(it);
	}
	ll mn = min(v, seg.qry(l, l));
	for(ll i = 0; i < V.size(); i++){
		ll t = r;
		if(i + 1 < V.size()) t = min(t, V[i + 1] - 1);
		if(mn < INF){
			ll e = seg.Go(V[i], t, mn);
			if(e != -1){
				seg.upd(V[i], e, mn);
			}
		}
		mn = min(mn, seg.qry(V[i], t));
	}
	Mx.insert(l);
	if(r != D - 1) Mx.insert(r + 1);
}

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

	fill(seg.Lz, seg.Lz + 4500005, 9e18);
    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();
	Mx.insert(0);
	if(D != 1) Mx.insert(1);
	seg.upd(1, D - 1, INF);
    for(auto e : Ev){
        if(e.t == 0){
            seg.upd(e.lx, e.rx, INF);
			auto it = Mx.lower_bound(e.lx);
			while(it != Mx.end()){
				if(*it > e.rx) break;
				it = Mx.erase(it);
			}
			Mx.insert(e.lx);
			if(e.rx != D - 1) Mx.insert(e.rx + 1);
        } else if(e.t == 1){
            if(e.lx == 0 && e.rx == S - 1){
				ll c = seg.qry(S - 1, S - 1) + (A * D - B) * (e.ri - e.li + 1);
				if(e.li + 1 <= e.ri) c = min(c, seg.qry(0, S - 1) + min(A * D - B, (A * D - B) * (e.ri - e.li)));
				Chmin(0, S - 1, c);
            } else {
                if(e.lx == 0) Chmin(e.lx, e.rx, seg.qry(S - 1, S - 1) + A * D - B);
				Chmin(e.lx, e.rx, INF);	
            }
        } else {
            ll q = seg.qry(e.lx, e.lx) + A * Coord[e.lx] + B * e.li;
            Ans[-e.t] = (q > MAX_ANS ? -1 : q);
        }
    }
    for(ll i = 1; i <= Q; i++){
    	cout << Ans[i] << '\n';
    }
}

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