Submission #274478

#TimeUsernameProblemLanguageResultExecution timeMemory
274478Atill83Santa Claus (RMI19_santa)C++14
30 / 100
1089 ms3644 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 1e5+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n; int x[MAXN], h[MAXN], v[MAXN]; int ans[MAXN]; bool check(int m, int i){ multiset<int> st; for(int j = i; j >= m; j--){ if(h[j]){ st.insert(v[j]); } } for(int j = i; j > 0; j--){ if(h[j] == 0){ auto u = st.upper_bound(v[j]); if(u == st.begin()) return 0; st.erase(prev(u)); }else if(j < m){ st.insert(v[j]); } } return 1; } void solve(){ set<int> elv; cin>>n; for(int i = 1; i <= n; i++){ cin>>x[i]; } int lst = 0; for(int i = 1; i <= n; i++){ cin>>h[i]; if(!h[i]) lst = i; } for(int i = 1; i <= n; i++){ cin>>v[i]; } int l = 1, r = n; while(l < r){ int m = (l + r + 1) / 2; if(check(m, n)){ l = m; }else{ r = m - 1; } } if(l == 1 && check(l, n) == 0){ for(int j = 1; j <= n; j++){ cout<<"-1 "; } }else{ ans[n] = 2*x[n] - x[l]; //cerr<<n<<endl; for(int j = n - 1; j > 0; j--){ if(j < lst){ ans[j] = -1; }else{ while(l && (l > j || !check(l, j))) l--; //cerr<<j<<" "<<l<<endl; if(l == 0){ ans[j] = -1; }else{ ans[j] = 2*x[j] - x[l]; } } } for(int j = 1; j <= n; j++){ cout<<ans[j]<<" "; } } cout<<endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin); freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout); #endif int t; cin>>t; while(t--) solve(); #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...