Submission #936637

#TimeUsernameProblemLanguageResultExecution timeMemory
936637koukirocksSnowball (JOI21_ho_t2)C++17
100 / 100
74 ms15444 KiB
#include <bits/stdc++.h> #define speed ios_base::sync_with_stdio(0); cin.tie(0) #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef double db; typedef long double ldb; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll MAX=2e5+10,P=998244353; const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f; ll n,q; ll pos[MAX]; pll dis[MAX]; pll rg[MAX]; int main() { speed; cin>>n>>q; for (int i=0;i<n;i++) { cin>>pos[i]; rg[i]={-1,-1}; if (i!=0) dis[i-1]={pos[i]-pos[i-1],i-1}; } sort(dis,dis+n-1); ll L=0,R=0; ll now=0; ll id=0; while (q--) { ll k; cin>>k; now+=k; if (now>R) { R=now; while (id<n-1 and dis[id].first<R-L) { // cout<<dis[id].first<<" "<<dis[id].second<<" id\n"; rg[dis[id].second].second=pos[dis[id].second+1]+L; rg[dis[id].second+1].first=pos[dis[id].second+1]+L; id++; } } else if (now<L) { L=now; while (id<n-1 and dis[id].first<R-L) { rg[dis[id].second+1].first=pos[dis[id].second]+R; rg[dis[id].second].second=pos[dis[id].second]+R; id++; } } // cout<<L<<" "<<R<<"\n"; } for (int i=0;i<n;i++) { // cout<<rg[i].first<<" "<<rg[i].second<<"\n"; if (rg[i].first==-1) rg[i].first=pos[i]+L; if (rg[i].second==-1) rg[i].second=pos[i]+R; cout<<rg[i].second-rg[i].first<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...