Submission #274791

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
274791	2020-08-19T15:45:11 Z	Atill83	Santa Claus (RMI19_santa)	C++14	100 / 100	370 ms	9080 KB

santa

#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 t[4*MAXN];
int lazy[4*MAXN];
void push(int v){
    t[2*v] += lazy[v];
    t[2*v + 1] += lazy[v];
    lazy[2*v] += lazy[v];
    lazy[2*v + 1] += lazy[v];
    lazy[v] = 0;
}




void upd(int v, int tl, int tr, int l, int r, int val){
    if(l > r) return;
    else if(l == tl && r == tr){
        lazy[v] += val;
        t[v] += val;

    }else{
        push(v);

        int tm = (tl + tr) / 2;

        upd(2*v, tl, tm, l, min(tm, r), val);
        upd(2*v + 1, tm + 1, tr, max(tm + 1, l), r, val);

        t[v] = min(t[2*v], t[2*v + 1]);
    }
}


int x[MAXN], h[MAXN], v[MAXN];
int cik[MAXN];
ll ans[MAXN];

void solve(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>x[i];
    }
    int lst = 0;
    memset(lazy, 0, sizeof(lazy));
    memset(t, 0, sizeof(t));
    multiset<int> ms;
    for(int i = 1; i <= n; i++){
        cin>>h[i];
        if(h[i] == 0) lst = i;
    }
    memset(cik, -1, sizeof(cik));
    for(int i = 1; i <= n; i++){
        cin>>v[i];
        if(h[i] == 0){
            ms.insert(v[i]);
        }else{
            auto u = ms.lower_bound(v[i]);
            if(u != ms.end()){
                cik[i] = *u;
                ms.erase(u);
            }
        }
    }

    for(int j: ms){
        upd(1, 0, n, j, n, -1);
    }
    int left = n;

    
    for(int i = n; i >= 1; i--){
        if(i < lst){
            ans[i] = -1;
        }else{
            while(left >= i || (t[1] < 0 && left)){
                if(cik[left] >= 0)
                    upd(1, 0, n, cik[left], n, -1);
                if(h[left])
                    upd(1, 0, n, v[left], n, 1);
                left--;
            }

            if(t[1] < 0){
                ans[i] = -1;
            }else{
                ans[i] = 2*x[i] - x[left + 1];
            }
            upd(1, 0, n, v[i], n, - 1);
        }
    }
    for(int i = 1; i <= n; i++) cout<<ans[i]<<" ";
    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
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3840 KB	Output is correct
2	Correct	4 ms	3840 KB	Output is correct
3	Correct	11 ms	3968 KB	Output is correct
4	Correct	29 ms	4096 KB	Output is correct
5	Correct	43 ms	4348 KB	Output is correct
6	Correct	68 ms	4728 KB	Output is correct
7	Correct	137 ms	5460 KB	Output is correct
8	Correct	229 ms	6136 KB	Output is correct
9	Correct	246 ms	7672 KB	Output is correct
10	Correct	370 ms	9080 KB	Output is correct