Submission #581611

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
581611	2022-06-22T21:24:33 Z	JovanB	Santa Claus (RMI19_santa)	C++17	100 / 100	250 ms	13252 KB

santa

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 100000;

struct Segment{
    int mn, sum;
} seg[4*N+5];

void mrg(int node){
    seg[node].sum = seg[node*2].sum + seg[node*2+1].sum;
    seg[node].mn = min(seg[node*2].mn, seg[node*2].sum + seg[node*2+1].mn);
}

void init(int node, int l, int r){
    seg[node].mn = seg[node].sum = 0;
    if(l == r) return;
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
}

void upd(int node, int l, int r, int x, int t){
    if(l == r){
        seg[node].mn += t;
        seg[node].sum += t;
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) upd(node*2, l, mid, x, t);
    else upd(node*2+1, mid+1, r, x, t);
    mrg(node);
}

multiset <int> q;
int sol[N+5];
int x[N+5], h[N+5], val[N+5];

void solve(){
    int n;
    cin >> n;
    init(1, 1, n + 1);
    for(int i=1; i<=n; i++){
        cin >> x[i];
    }
    int last = 0;
    for(int i=1; i<=n; i++){
        cin >> h[i];
        if(!h[i]) last = i;
    }
    for(int i=1; i<=n; i++){
        cin >> val[i];
        val[i]++;
    }
    for(int i=1; i<=last; i++){
        if(h[i]) upd(1, 1, n + 1, val[i], 1);
        else upd(1, 1, n + 1, val[i], -1);
    }
    q.clear();
    int j = 1;
    for(int i=last; i<=n; i++){
        if(i != last) upd(1, 1, n + 1, val[i], 1);
        while(j < i){
            if(!h[j]){
                q.insert(val[j]);
                j++;
                continue;
            }
            auto c = q.lower_bound(val[j]);
            if(c == q.end()){
                upd(1, 1, n + 1, val[j], -1);
                if(seg[1].mn < 0){
                    upd(1, 1, n + 1, val[j], 1);
                    break;
                }
                j++;
                continue;
            }
            upd(1, 1, n + 1, *c, 1);
            upd(1, 1, n + 1, val[j], -1);
            if(seg[1].mn >= 0) q.erase(c);
            else{
                upd(1, 1, n + 1, *c, -1);
                upd(1, 1, n + 1, val[j], 1);
                break;
            }
            j++;
        }
        if(seg[1].mn < 0) sol[i] = -1;
        else sol[i] = 2*x[i] - x[j];
    }
    for(int i=1; i<=n; i++){
        if(i < last) cout << "-1 ";
        else cout << sol[i] << " ";
    }
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	6 ms	596 KB	Output is correct
4	Correct	18 ms	904 KB	Output is correct
5	Correct	30 ms	1540 KB	Output is correct
6	Correct	48 ms	2404 KB	Output is correct
7	Correct	110 ms	4504 KB	Output is correct
8	Correct	143 ms	6944 KB	Output is correct
9	Correct	188 ms	10192 KB	Output is correct
10	Correct	250 ms	13252 KB	Output is correct