Submission #891678

#TimeUsernameProblemLanguageResultExecution timeMemory
891678hafoSnowball (JOI21_ho_t2)C++14
0 / 100
1 ms4444 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define pb push_back #define pa pair<int, int> #define pall pair<ll, int> #define fi first #define se second #define TASK "test" #define Size(x) (int) x.size() #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;} template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;} const int MOD = 1e9 + 7; const int LOG = 20; const int maxn = 2e5 + 7; const ll oo = 1e18 + 69; int n, t, p[maxn], idl[maxn], idr[maxn]; ll x[maxn], w, res[maxn], cntl, cntr, cnt; priority_queue<pall, vector<pall>, greater<pall>> q; int find_node(int u) { return p[u] < 0 ? u:p[u] = find_node(p[u]); } void do_l() { w = -w; cnt -= w; while(Size(q) && q.top().fi <= w) { auto top = q.top(); q.pop(); int u = top.se; int v = u + 1; u = find_node(u); v = find_node(v); // hop v vao u res[idl[v]] += top.fi - cntr; res[idr[u]] += cntr; p[u] += p[v]; p[v] = u; idr[u] = idr[v]; } if(cnt > 0) maxi(cntr, cnt); if(cnt < 0) maxi(cntl, -cnt); } void do_r() { cnt += w; while(Size(q) && q.top().fi <= w) { auto top = q.top(); q.pop(); int u = top.se; int v = top.se + 1; u = find_node(u); v = find_node(v); // hop u vao v res[idr[u]] += top.fi - cntl; res[idl[v]] += cntl; p[v] += p[u]; p[u] = v; idl[v] = idl[u]; } if(cnt > 0) maxi(cntr, cnt); if(cnt < 0) maxi(cntl, -cnt); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); cin>>n>>t; for(int i = 1; i <= n; i++) { cin>>x[i]; p[i] = -1; idl[i] = idr[i] = i; } for(int i = 1; i < n; i++) { q.push({x[i + 1] - x[i], i}); } while(t--) { cin>>w; if(w < 0) do_l(); else do_r(); } for(int i = 1; i <= n; i++) { if(find_node(i) == i) { res[idl[i]] += cntl; res[idr[i]] += cntr; } } for(int i = 1; i <= n; i++) cout<<res[i]<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...