Submission #1209348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209348		lighton	Tower (JOI24_tower)	C++20	43 / 100	2066 ms	117220 KiB

Main

#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
ll N,Q,D,A,B;
ll L[200001],R[200001],G[200001];
vector<ll> X,Y;
vector<array<ll,2> > block[1000001];
vector<array<ll,2> > query[1000001];
ll ans[1000001];

struct Seg{
    ll arr[4000001];
    ll lazy[4000001];
    void propagate(int now, int s, int e){
        if(lazy[now] != -2*inf){
            arr[now] = lazy[now];
            if(s!=e){lazy[now*2] = lazy[now], lazy[now*2+1] = lazy[now];}
            lazy[now] = -2*inf;
        }
    }
    void update(int now, int s, int e, int l, int r, ll x){
        if(l>r) return;
        propagate(now,s,e);
        if(l<=s && e<=r){
            arr[now] = x;
            if(s!=e){ lazy[now*2]=x; lazy[now*2+1]=x;}
            return;
        }
        if(l>e || r<s) return;
        int m = s+e>>1;
        update(now*2,s,m,l,r,x); update(now*2+1,m+1,e,l,r,x);
        arr[now] = max(arr[now*2],arr[now*2+1]);
    }
    ll query(int now, int s, int e, int l, int r){
        if(l>r) return -inf;
        propagate(now,s,e);
        if(l<=s && e<=r) return arr[now];
        if(l>e || r<s) return -inf;
        int m = s+e>>1;
        return max(query(now*2,s,m,l,r) , query(now*2+1,m+1,e,l,r));
    }
} seg;

void upd(int now, ll v){
    int l = now-1, r = sz(X)+1;
    while(l+1<r){
        int m = l+r>>1;
        if(seg.query(1,1,sz(X), now,m) > v) r = m;
        else l = m;
    }
    seg.update(1,1,sz(X),now,l,v);
}

int main(){
    IO
    cin>>N>>Q>>D>>A>>B;
    forf(i,1,N) {
        cin >> L[i] >> R[i];
        X.pb({L[i] % D}), X.pb({R[i] % D}), X.pb({(L[i]-1)%D}), X.pb({(R[i]+1)%D});
        Y.pb({L[i]/D}), Y.pb({L[i]/D + 1}); if(L[i]/D != 0) Y.pb({L[i]/D-1});
    }
    forf(i,1,Q) cin>>G[i], X.pb({G[i]%D}), Y.pb({G[i]/D});
    X.pb(0), X.pb(D-1), Y.pb(0);
    sort(all(X)), comp(X), sort(all(Y)), comp(Y);

    forf(i,1,N){
        if(L[i]/D != R[i]/D) {
            block[idx(L[i] / D, Y)].pb({idx(L[i] % D ,X), sz(X)-1});
            if(R[i]-L[i]+1 >= D) block[idx(L[i]/D + 1, Y)]. pb({0,sz(X)-1});
            else block[idx(L[i] / D + 1,Y)].pb({0, idx(R[i]%D, X)});
        }
        else block[idx(L[i] / D, Y)].pb({idx(L[i] % D ,X), idx(R[i] % D ,X)});
    }
    forf(i,1,Q) query[idx(G[i]/D,Y)].pb({idx(G[i]%D, X), i});
    forf(i,0,sz(Y)-1) sort(all(block[i]));

    forf(i,0,1) fill(seg.lazy, seg.lazy+4*sz(X), -2*inf);
    seg.update(1,1,sz(X),1,sz(X),-inf);
    ll dir = 1;
    if(A*D < B) dir = -1;

    forf(y,0,sz(Y)-1){
        ll step = 1;
        if(y != 0) step = Y[y] - Y[y-1];
        int f = 0; ll v;

        if(y==0) f = 1, v = 0;
        else if(seg.query(1,1,sz(X),sz(X),sz(X)) != -inf){
            f = 1, v = seg.query(1,1,sz(X),sz(X),sz(X));
            if(dir == 1) v--;
            else v += step;
        }

        for(auto [s,e] : block[y]) seg.update(1,1,sz(X),s+1,e+1,inf);
        if(y != 0){
            for(auto [s,e] : block[y-1]){
                if(s!= 0 && seg.query(1,1,sz(X),s,s) != inf) upd(s, seg.query(1,1,sz(X),s,s));
            }
        }

        if(f) upd(1,v);

        for(auto [s,e] : block[y]) seg.update(1,1,sz(X),s+1,e+1,-inf);

        //forf(i,1,sz(X)) cout<<seg.query(1,1,sz(X),i,i)<<" ";
        //cout<<"\n";
        for(auto [x,i] : query[y]){
            if(seg.query(1,1,sz(X),x+1,x+1) <= -inf/2) ans[i] = -inf;
            else if(dir == 1) ans[i] = seg.query(1,1,sz(X),x+1,x+1) + Y[y];
            else ans[i] = -seg.query(1,1,sz(X),x+1,x+1) + Y[y];
        }
    }

    forf(i,1,Q){
        if(ans[i] <= -inf/2) cout<<"-1\n";
        else cout<<ans[i]*B + (G[i]-ans[i]*D)*A <<"\n";
    }
}

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