# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
219246 | 2fat2code | Santa Claus (RMI19_santa) | C++17 | 401 ms | 8696 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sz() size()
#define fr first
#define sc second
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;
const int mod=1e9+7;
const int modp=1999999973;
const int modulo=998244353;
const int nmax=100005;
int t,n,x[nmax],v[nmax],tree[4*nmax],lazy[4*nmax];
bitset<nmax>h;
void build(int l,int r,int nod){
if(l==r){
tree[nod]=lazy[nod]=0;
}
else{
int mid=l+(r-l)/2;
tree[nod]=lazy[nod]=0;
build(l,mid,2*nod);
build(mid+1,r,2*nod+1);
}
return;
}
void push(int l,int r,int nod){
if(lazy[nod]!=0){
tree[nod]+=lazy[nod];
if(l!=r){
lazy[2*nod]+=lazy[nod];
lazy[2*nod+1]+=lazy[nod];
}
lazy[nod]=0;
}
return;
}
void update(int l,int r,int le,int re,int val,int nod){
push(le,re,nod);
if(l>re || r<le) return;
else if(le>=l && re<=r){
lazy[nod]+=val;
push(le,re,nod);
return;
}
else{
int mid=le+(re-le)/2;
update(l,r,le,mid,val,2*nod);
update(l,r,mid+1,re,val,2*nod+1);
tree[nod]=min(tree[2*nod],tree[2*nod+1]);
return;
}
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
srand(chrono::steady_clock::now().time_since_epoch().count());
// ifstream cin("input.in");
// ofstream cout("outputut.out");
cin >> t;
while(t--){
int lastelf=0;
build(1,nmax,1);
cin >> n;
for(int i=1;i<=n;i++) cin >> x[i];
for(int i=1;i<=n;i++){
int tz;
cin >> tz;
h[i]=tz;
if(h[i]==0) lastelf=i;
}
for(int i=1;i<=n;i++) {
cin >> v[i];
++v[i];
}
int left_max=0,curr=1;
if(h[1]==0) update(v[1],nmax,1,nmax,-1,1);
if(h[1]==1) update(v[1],nmax,1,nmax,1,1);
while(curr<=n && (curr<lastelf || tree[1]<0)){
cout << "-1 ";
++curr;
if(curr<=n){
if(h[curr]==0) update(v[curr],nmax,1,nmax,-1,1);
if(h[curr]==1) update(v[curr],nmax,1,nmax,1,1);
}
}
if(curr<=n){
multiset<int>gifts;
for(int i=curr;i<=n;i++){
bool ok=false;
do{
if(left_max>=(i-1)) break;
ok=false;
if(h[left_max+1]==1){
update(v[left_max+1],nmax,1,nmax,-1,1);
auto it=gifts.lower_bound(v[left_max+1]);
if(it!=gifts.end()){
update(*it,nmax,1,nmax,1,1);
if(tree[1]>=0){
ok=true;
gifts.erase(it);
left_max++;
}
else{
update(*it,nmax,1,nmax,-1,1);
update(v[left_max+1],nmax,1,nmax,1,1);
}
}
else{
if(tree[1]>=0){
left_max++;
ok=true;
}
else update(v[left_max+1],nmax,1,nmax,1,1);
}
}
else{
left_max++;
gifts.insert(v[left_max]);
ok=true;
}
}while(ok==true);
if(i+1<=n) update(v[i+1],nmax,1,nmax,1,1);
cout << 2LL*x[i] - x[left_max+1] << ' ';
}
}
cout << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |