Submission #1230388

#TimeUsernameProblemLanguageResultExecution timeMemory
1230388DangKhoizzzzSnowball (JOI21_ho_t2)C++20
33 / 100
1523 ms17776 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second #define pii pair <int , int> #define arr4 array <int , 4> using namespace std; const int INF = 2e17 + 99; const int maxn = 2e5 + 7; int n , q , a[maxn] , L[maxn] , R[maxn] , ansL[maxn] , ansR[maxn] , b[maxn] , x[maxn]; priority_queue <arr4 , vector <arr4> , greater <arr4>> Q; void check1() { int dis = 0 , mx = 0; for(int i = 1; i <= q; i++) { dis += b[i]; if(dis < 0) mx = max(mx , dis*-1); else { while(!Q.empty() && Q.top()[0] <= dis) { int w = Q.top()[1]; int mid = Q.top()[2]; int id = Q.top()[3]; Q.pop(); if(w <= mx) { ansL[id] = w; R[id] = mid - 1; } else L[id] = mid + 1; } } } while(!Q.empty()) { int id = Q.top()[3] , mid = Q.top()[2] , w = Q.top()[1]; if(w <= mx) { ansL[id] = w; R[id] = mid - 1; } else L[id] = mid + 1; Q.pop(); } } void check2() { int dis = 0 , mx = 0; for(int i = 1; i <= q; i++) { dis += b[i]; if(dis >= 0) mx = max(mx , dis); else { while(!Q.empty() && Q.top()[0] <= dis*-1) { int w = Q.top()[1]; int mid = Q.top()[2]; int id = Q.top()[3]; Q.pop(); if(w <= mx) { ansR[id] = w; L[id] = mid + 1; } else R[id] = mid - 1; } } } while(!Q.empty()) { int id = Q.top()[3] , mid = Q.top()[2] , w = Q.top()[1]; if(w <= mx) { ansR[id] = w; L[id] = mid + 1; } else R[id] = mid - 1; Q.pop(); } } void solve() { cin >> n >> q; for(int i = 1; i <= n; i++) cin >> x[i]; for(int i = 1; i <= q; i++) cin >> b[i]; x[0] = -INF; x[n+1] = INF; for(int i = 1; i <= n; i++) L[i] = x[i-1] , R[i] = x[i] , ansL[i] = 0; for(int _ = 0; _ <= 62; _++) { while(!Q.empty()) Q.pop(); for(int i = 1; i <= n; i++) { if(L[i] <= R[i]) { int mid = (L[i] + R[i])/2; //cout << L[i] << ' ' << R[i] << ' ' << mid << '\n'; Q.push({mid - x[i-1] + 1 , x[i] - mid , mid , i}); } } check1(); } for(int i = 1; i <= n; i++) L[i] = x[i] , R[i] = x[i+1] , ansR[i] = 0; for(int _ = 0; _ <= 62; _++) { while(!Q.empty()) Q.pop(); for(int i = 1; i <= n; i++) { if(L[i] <= R[i]) { int mid = (L[i] + R[i])/2; Q.push({x[i+1] - mid + 1 , mid - x[i] , mid , i}); } } check2(); } for(int i = 1; i <= n; i++) cout << ansR[i] + ansL[i] << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...