Submission #951133

#TimeUsernameProblemLanguageResultExecution timeMemory
951133veljkoSnowball (JOI21_ho_t2)C++17
0 / 100
462 ms197248 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); } }; /*Steps 1. Initialize the tree 2. Initialize the identity element along with size 3. Build it 4. Query 5. Update*/ 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]); } // 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); map<int, int>mp; forn(i,q){ if (mp.find(dif[i]) == mp.end()) mp[dif[i]] = i; } //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 = true; int bad = (a[i+1] - a[i]) - mid; for (auto t : dif){ if (t >= mid) break; if (-t > bad){ ok = false; break; } } 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; //cout <<bad<<'\n'; bool ok = true; for (auto t : dif){ if (-t >= mid) break; if (t > bad){ ok = false; break; } } if (ok){ l = mid + 1; x = mid; } else r = mid - 1; } 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); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif 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:130:46: warning: unused variable 'y' [-Wunused-variable]
  130 |         int l = 0, r = a[i+1] - a[i], x = 0, y = 0;
      |                                              ^
Main.cpp: In function 'int32_t main()':
Main.cpp:182:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:183:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...