제출 #1041096

#제출 시각아이디문제언어결과실행 시간메모리
1041096Alihan_8사탕 분배 (IOI21_candies)C++17
29 / 100
97 ms22460 KiB
#include "candies.h" #include <vector> #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define ar array #define pb push_back #define ln '\n' //#define int long long using i64 = long long; template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } const i64 inf = 1e15; std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) { int q = l.size(), n = c.size(); // subtask #4 vector <int> p; for ( int j = 0; j < q; j++ ){ p.pb(j); } int m = p.size(); vector <ar<i64,3>> H; vector <i64> pf(m + 1); { // calc updates stack <int> s1, s2; s1.push(-1), s2.push(-1); vector <int> mn, mx; mn = mx = {0}; for ( int j = 1; j <= m; j++ ){ int u = p[j - 1]; pf[j] = pf[j - 1] + v[u]; while ( s1.size() > 1 && pf[s1.top()] >= pf[j] ) s1.pop(); while ( s2.size() > 1 && pf[s2.top()] <= pf[j] ) s2.pop(); { // min case int it = lower_bound(all(mx), s1.top() + 1) - mx.begin(); if ( it < (int)mx.size() ){ i64 df = pf[mx[it]] - pf[j]; H.pb({df, j, 0}); } } { // max case int it = lower_bound(all(mn), s2.top() + 1) - mn.begin(); if ( it < (int)mn.size() ){ i64 df = pf[j] - pf[mn[it]]; H.pb({df, j, 1}); } } s1.push(j), s2.push(j); while ( !mn.empty() && pf[mn.back()] >= pf[j] ){ mn.pop_back(); } while ( !mx.empty() && pf[mx.back()] <= pf[j] ){ mx.pop_back(); } mn.pb(j), mx.pb(j); } } sort(all(H)); reverse(all(H)); vector <ar<int,2>> lst(n, {-1, -1}); { // finding lst vector <int> p(n); iota(all(p), 0); sort(all(p), [&](int &u, int &v){ return c[u] > c[v]; }); ar <int,2> mx = {-1, -1}; int j = 0; for ( auto &i: p ){ while ( j < (int)H.size() && H[j][0] >= c[i] ){ chmax(mx, ar <int,2> {(int)H[j][1], (int)H[j][2]}); j++; } lst[i] = mx; } } i64 lft = pf.back() - *min_element(all(pf)); vector <i64> sf(m + 2); for ( int i = m; i > 0; i-- ){ sf[i] = sf[i + 1] + v[p[i - 1]]; } vector <int> ans(n); for ( int i = 0; i < n; i++ ){ //~ cout << lst[i][0] << " " << lst[i][1] << ln; if ( lst[i][0] == -1 ){ ans[i] = lft; } else{ ans[i] = sf[lst[i][0] + 1] + lst[i][1] * c[i]; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...