Submission #219246

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
219246	2020-04-04T17:59:33 Z	2fat2code	Santa Claus (RMI19_santa)	C++17	100 / 100	401 ms	8696 KB

santa

#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';
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	4480 KB	Output is correct
2	Correct	11 ms	4480 KB	Output is correct
3	Correct	18 ms	4608 KB	Output is correct
4	Correct	30 ms	4704 KB	Output is correct
5	Correct	56 ms	4856 KB	Output is correct
6	Correct	81 ms	5240 KB	Output is correct
7	Correct	145 ms	5880 KB	Output is correct
8	Correct	224 ms	6496 KB	Output is correct
9	Correct	286 ms	7884 KB	Output is correct
10	Correct	401 ms	8696 KB	Output is correct