Submission #1209346

#TimeUsernameProblemLanguageResultExecution timeMemory
1209346lightonTower (JOI24_tower)C++20
0 / 100
2098 ms117220 KiB
#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(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"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...