Submission #951148

#TimeUsernameProblemLanguageResultExecution timeMemory
951148veljkoSnowball (JOI21_ho_t2)C++17
100 / 100
918 ms45876 KiB
/*****from dust I have come, dust I will be*****/ #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define int long long #define forn(i,n) for(int i=0;i<n;i++) int dx[8] = { 1, 0, -1, 0, -1, 1, -1, 1 }; int dy[8] = { 0, 1, 0, -1, -1, 1, 1, -1 }; int ceil_div(int a, int b) {return a % b == 0 ? a / b : a / b + 1;} const int MOD = 1000000007; //const int MOD = 998244353; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key /* int k = A.order_of_key(p[i].second); A.erase(A.find_by_order(k)); erase element from pbds multiset */ template<class T> struct segtree { vector<T> st; int n; T identity_element; segtree(int n, T identity_element) { this->n = n; this->identity_element = identity_element; st.assign(4 * n, identity_element); } T combine(T l, T r) { // Change this function as required. T ans; ans.maxval=max(l.maxval,r.maxval); ans.minval=min(l.minval,r.minval); return ans; } void buildUtil(int v, int tl, int tr, vector<T>& a) { if (tl == tr) { st[v] = a[tl]; return; } int tm = (tl + tr) >> 1; buildUtil(2 * v + 1, tl, tm, a); buildUtil(2 * v + 2, tm + 1, tr, a); st[v] = combine(st[2 * v + 1], st[2 * v + 2]); } T queryUtil(int v, int tl, int tr, int l, int r) { if (l > r) return identity_element; if (tr < l or tl > r) { return identity_element; } if (l <= tl and r >= tr) { return st[v]; } int tm = (tl + tr) >> 1; return combine(queryUtil(2 * v + 1, tl, tm, l, r), queryUtil(2 * v + 2, tm + 1, tr, l, r)); } void updateUtil(int v, int tl, int tr, int pos, T upd) { if (tr < pos or tl > pos) return; if (tl == tr) { st[v] = upd; return; } int tm = (tl + tr) >> 1; updateUtil(2 * v + 1, tl, tm, pos, upd); updateUtil(2 * v + 2, tm + 1, tr, pos, upd); st[v] = combine(st[2 * v + 1], st[2 * v + 2]); } void build(vector<T> a) { assert((int)a.size() == n); buildUtil(0, 0, n - 1, a); } T query(int l, int r) { return queryUtil(0, 0, n - 1, l, r); } void update(int pos, T upd) { updateUtil(0, 0, n - 1, pos, upd); } }; struct node{ int maxval; int minval; }; void solve(){ int n, q; cin >> n>> q; vector<int>a(n); for (auto &t : a) cin >> t; vector<int>b(q); for (auto &t : b) cin >> t; vector<int>dif; forn(i,q){ if (i == 0) dif.push_back(b[0]); else dif.push_back(dif.back() + b[i]); } map<int, int>mp; forn(i,q){ if (mp.find(dif[i]) == mp.end()) mp[dif[i]] = i; } vector<int>neg; int mn = 0; for (auto t : dif){ mn = min(mn, t); neg.push_back(mn); } for (auto &t : neg) t *= -1; vector<int>pos; int mx = 0; for (auto t : dif){ mx = max(mx, t); pos.push_back(mx); } // for (auto t : neg) cout <<t<<' '; // cout <<'\n'; // for (auto t : dif) cout <<t<<' '; // cout <<'\n'; segtree<node> st(q,{0,LONG_LONG_MAX}); vector<node> temp; for(auto t : dif) temp.push_back({t,t}); st.build(temp); //for (auto t : mp) cout <<t.first<<' '<<t.second<<'\n'; vector<int>ans(n, 0); for (int i=0;i<n-1;i++){ int l = 0, r = a[i+1] - a[i], x = 0, y = 0; while (l <= r){ int mid = (l + r) / 2; bool ok; auto it = lower_bound(pos.begin(), pos.end(), mid); int bad = (a[i+1] - a[i]) - mid; if (it == pos.end()) ok = false; else{ int index = it - pos.begin(); //if (index == 2) cout <<mn<<'\n'; int mn = neg[index]; if (mn > bad) ok = false; else ok = true; } if (ok){ l = mid + 1; x = mid; } else r = mid - 1; } ans[i] += x; } ans[n-1] += max(*max_element(dif.begin(), dif.end()), 0ll); for (int i=1;i<n;i++){ int l = 0, r = a[i] - a[i-1], x = 0; while (l <= r){ int mid = (l + r) / 2; int bad = (a[i] - a[i-1]) - mid; bool ok; auto it = lower_bound(neg.begin(), neg.end(), mid); if (it == neg.end()) ok = false; else{ int index = it - neg.begin(); // if (mid == 2) cout <<index<<'\n'; int mx = pos[index]; if (mx > bad) ok = false; else ok = true; } if (ok){ l = mid + 1; x = mid; } else r = mid - 1; } //cout <<x<<'\n'; ans[i] += x; } ans[0] += max(0ll, *min_element(dif.begin(), dif.end()) * - 1); for (auto t : ans) cout <<t<<'\n'; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >>t; for (int i=1;i<=t;i++){ solve(); } return 0; }

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:137:46: warning: unused variable 'y' [-Wunused-variable]
  137 |         int l = 0, r = a[i+1] - a[i], x = 0, y = 0;
      |                                              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...