Submission #274478

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
274478	2020-08-19T12:12:46 Z	Atill83	Santa Claus (RMI19_santa)	C++14	30 / 100	1000 ms	3644 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 x[MAXN], h[MAXN], v[MAXN];
int ans[MAXN];
bool check(int m, int i){
    multiset<int> st;


    for(int j = i; j >= m; j--){
        if(h[j]){
            st.insert(v[j]);
        }
    }
    for(int j = i; j > 0; j--){
        if(h[j] == 0){
            auto u = st.upper_bound(v[j]);
            if(u == st.begin()) return 0;
            st.erase(prev(u));
        }else if(j < m){
            st.insert(v[j]);
        }
    }
    return 1;

}

void solve(){
    set<int> elv;
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>x[i];
    }
    int lst = 0;
    for(int i = 1; i <= n; i++){
        cin>>h[i];
        if(!h[i]) 
            lst = i;
    }
    
    for(int i = 1; i <= n; i++){
        cin>>v[i];
    }
    
    int l = 1, r = n;
    while(l < r){
        int m = (l + r + 1) / 2;
        if(check(m, n)){
            l = m;
        }else{
            r = m - 1;
        }
    }
    if(l == 1 && check(l, n) == 0){
        for(int j = 1; j <= n; j++){
            cout<<"-1 ";
        }
    }else{
        ans[n] = 2*x[n] - x[l];
        //cerr<<n<<endl;
        for(int j = n - 1; j > 0; j--){
            if(j < lst){
                ans[j] = -1;
            }else{
                while(l && (l > j || !check(l, j))) l--;
                //cerr<<j<<" "<<l<<endl;
                if(l == 0){
                    ans[j] = -1;
                }else{
                    ans[j] = 2*x[j] - x[l];
                }
            }
        }
        for(int j = 1; j <= n; j++){
            cout<<ans[j]<<" ";
        }

    }
    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

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	11 ms	512 KB	Output is correct
3	Correct	812 ms	544 KB	Output is correct
4	Execution timed out	1085 ms	760 KB	Time limit exceeded
5	Execution timed out	1085 ms	632 KB	Time limit exceeded
6	Execution timed out	1083 ms	768 KB	Time limit exceeded
7	Execution timed out	1089 ms	1332 KB	Time limit exceeded
8	Execution timed out	1087 ms	1792 KB	Time limit exceeded
9	Execution timed out	1081 ms	3576 KB	Time limit exceeded
10	Execution timed out	1045 ms	3644 KB	Time limit exceeded