Submission #942064

#TimeUsernameProblemLanguageResultExecution timeMemory
942064dsyzSnowball (JOI21_ho_t2)C++17
0 / 100
1 ms604 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define MAXN (1000005) struct node{ ll s,e,m,v,lazy; node *l = nullptr, *r = nullptr; node(ll _s,ll _e){ s = _s; e = _e; m = (s + e) / 2; v = 0; lazy = -1e18; } void create(){ if(l == nullptr && s != e){ l = new node(s,m); r = new node(m + 1,e); } } void propo(){ create(); if(lazy == -1e18) return; v = (e-s+1) * lazy; if(s != e){ l->lazy = lazy; r->lazy = lazy; } lazy = -1e18; } void update(ll x,ll y,ll nval){ propo(); if(s == x && e == y){ lazy = nval; }else{ create(); if(x > m) r->update(x,y,nval); else if(y <= m) l->update(x,y,nval); else l->update(x,m,nval), r->update(m + 1,y,nval); l->propo(), r->propo(); v = l->v + r->v; } } ll query(ll x,ll y){ create(); propo(); if(s == x && e == y){ return v; }else{ if(x > m) return r->query(x,y); else if(y <= m) return l->query(x,y); else return l->query(x,m) + r->query(m+1,y); } } } *root; int main() { ios_base::sync_with_stdio(false);cin.tie(0); ll N,Q; cin>>N>>Q; root = new node(0,2e6 + 10); root -> update(0,2e6 + 10,1); ll X[N]; for(ll i = 0;i < N;i++){ cin>>X[i]; X[i] += (1e6 + 5); } ll ans[N]; memset(ans,0,sizeof(ans)); ll wind[Q]; for(ll q = 0;q < Q;q++){ cin>>wind[q]; if(wind[q] > 0){ //blow right for(ll i = N - 1;i >= 0;i--){ ans[i] += root -> query(X[i],X[i] + wind[q] - 1); root -> update(X[i],X[i] + wind[q] - 1,0); X[i] += wind[q]; } }else if(wind[q] < 0){ //blow left wind[q] *= -1; for(ll i = 0;i < N;i++){ ans[i] += root -> query(X[i] - wind[q],X[i] - 1); root -> update(X[i] - wind[q],X[i] - 1,0); X[i] -= wind[q]; } } } for(ll i = 0;i < N;i++){ cout<<ans[i]<<'\n'; } cout<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...