Submission #274790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
274790	2020-08-19T15:43:35 Z	Atill83	Santa Claus (RMI19_santa)	C++14	90 / 100	1000 ms	9208 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 build(int v, int l, int r){
    if(l == r){
        t[v] = 0;
        lazy[v] = 0;
    }else{
        build(2*v, l, (l + r) / 2);
        build(2*v + 1, (l + r) / 2 + 1, r);
        t[v] = 0;
        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];
            }
            cerr<<left<<" ";
            upd(1, 0, n, v[i], n, - 1);
        }
    }
    for(int i = 1; i <= n; i++) cout<<ans[i]<<" ";
    cout<<endl;
    cerr<<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

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3840 KB	Output is correct
2	Correct	8 ms	3840 KB	Output is correct
3	Correct	40 ms	4096 KB	Output is correct
4	Correct	100 ms	4472 KB	Output is correct
5	Correct	192 ms	5112 KB	Output is correct
6	Correct	287 ms	5588 KB	Output is correct
7	Correct	506 ms	6536 KB	Output is correct
8	Correct	764 ms	7672 KB	Output is correct
9	Correct	944 ms	9080 KB	Output is correct
10	Execution timed out	1099 ms	9208 KB	Time limit exceeded