Submission #702189

#TimeUsernameProblemLanguageResultExecution timeMemory
702189nicky4321Snowball (JOI21_ho_t2)C++14
0 / 100
1 ms468 KiB
//#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #include<bits/stdc++.h> #define ll long long #define ld long double #define F first #define S second #define PB push_back #define pii pair<int, int> #define pll pair<ll, ll> #define pdd pair<double, double> #define ALL(x) x.begin(), x.end() #define SZ(x) (int)x.size() #define vi vector<int> #define vl vector<ll> #define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++) #define IOS ios_base::sync_with_stdio(false); cin.tie(0); using namespace std; const int MAX = 1 << 20, MOD = 1e9 + 7; ll a[MAX], ans[MAX]; pll rng[MAX]; void solve(){ int n, q; cin >> n >> q; for(int i = 1;i <= n;i++){ cin >> a[i]; } ll mx = 0, mn = 0, now = 0; for(int i = 1;i <= q;i++){ ll x; cin >> x; now += x; mx = max(mx, now); mn = min(mn, now); rng[i] = {mn, mx}; cout << i << " " << mn << " " << mx << '\n'; } ans[1] = -rng[q].F; ans[n] = rng[q].S; for(int i = 1;i < n;i++){ ll l = 0, r = q + 1; while(l < r){ int mid = (r - l) / 2 + l; if(a[i] + rng[mid].S <= a[i + 1] + rng[mid].F) l = mid + 1; else r = mid; } l--; // cout << i << " " << l << '\n'; ans[i] += rng[l].S; ans[i + 1] += -rng[l].F; if(l == q) continue; if(rng[l + 1].S > rng[l].S) ans[i] += (rng[l + 1].F + a[i + 1]) - (rng[l].S + a[i]); else ans[i + 1] += (a[i + 1] + rng[l].F) - (a[i] + rng[l].S); } for(int i = 1;i <= n;i++) cout << ans[i] << '\n'; } int main(){ IOS // CASE solve(); return 0; } /* 10 10 -56 -43 -39 -31 -22 -5 0 12 18 22 -3 0 5 -4 -2 10 -13 -1 9 6 1 -3 0 2 -3 0 3 -3 2 4 -3 2 5 -4 2 6 -4 6 7 -7 6 8 -8 6 9 -8 6 10 -8 7 1 7 2 2 3 5 4 5 5 9 6 4 7 6 8 5 9 2 14 8 7 9 13 10 9 8 5 10 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...