Submission #396128

#TimeUsernameProblemLanguageResultExecution timeMemory
396128Knps4422Snowball (JOI21_ho_t2)C++14
0 / 100
2562 ms332 KiB
//#pragma optimization_level 3 //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include<bits/stdc++.h> /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/detail/standard_policies.hpp> using namespace __gnu_pbds; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset; */ #define fr first #define sc second #define vec vector #define pb push_back #define pii pair<int, int> #define forn(x,y) for(int x = 1 ; x <= (int)y ; ++x) #define all(x) (x).begin(),(x).end() #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0); using namespace std; typedef long long ll; typedef unsigned int uint; typedef pair<ll,ll> pll; typedef complex<int> point; const int nmax = 400005; const ll linf = 1e18; const ll mod = 998244353; const int inf = 1e9; const int sq = 5000; int n, q; ll pos[nmax], wind[nmax]; ll lef[nmax], rig[nmax]; ll cnt[nmax]; int main(){ cin >> n >> q; for (int i = 0; i < n; ++i) { cin >> pos[i]; } ll ps = 0; for (int i = 0; i < q; ++i) { cin >> wind[i]; ps += wind[i]; rig[i] = max(rig[i] , ps); rig[i+1] = rig[i]; lef[i] = min(lef[i] , ps); lef[i+1] = lef[i]; } cnt[0] -= lef[q-1]; cnt[n-1] += rig[q-1]; for(int i = 0; i < n; i++){ ll l = pos[i] , r = pos[i+1]; while(l < r){ ll mid = (l+r)/2; int lt = 0, rt = n-1; while(lt < rt){ int md = (lt+rt)/2; if(pos[i] + rig[md] - 1 >= mid){ rt = md; }else{ lt = md+1; } } int t1 = lt; lt = 0, rt = n-1; while(lt < rt){ int md = (lt+rt)/2; if(pos[i+1] + lef[md] <= mid){ rt = md; }else{ lt = md+1; } } int t2 = lt; if(t1 < t2){ l = mid+1; }else{ r = mid; } } //cout << i << ' ' << l << '\n'; cnt[i] += l - pos[i]; cnt[i+1] += pos[i+1] - l; } for(int i = 0; i < n; i++){ cout << cnt[i] << '\n'; } cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...