Submission #274332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
274332	2020-08-19T11:03:11 Z	Atill83	Santa Claus (RMI19_santa)	C++14	20 / 100	1000 ms	2936 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];

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];

    for(int i = 1; i <= n; i++){

        if(i < lst){
            cout<<"-1 ";
        }else{
            bool tru = 1;
            int l = 1, r = i;
            while(l < r){
                int m = (l + r + 1) / 2;
                if(check(m, i)){
                    l = m;
                }else
                {
                    r = m - 1;
                }
            
            }
            if(!check(l, i)){
                cout<<"-1 ";
            }else{
                cout<<2*x[i] - x[l]<<" ";
            }
        }
    }
    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
}

Compilation message

santa.cpp: In function 'void solve()':
santa.cpp:62:18: warning: unused variable 'tru' [-Wunused-variable]
   62 |             bool tru = 1;
      |                  ^~~

Subtask #1

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	30 ms	384 KB	Output is correct
3	Execution timed out	1053 ms	384 KB	Time limit exceeded
4	Execution timed out	1048 ms	468 KB	Time limit exceeded
5	Execution timed out	1091 ms	556 KB	Time limit exceeded
6	Execution timed out	1093 ms	640 KB	Time limit exceeded
7	Execution timed out	1094 ms	1024 KB	Time limit exceeded
8	Execution timed out	1086 ms	1660 KB	Time limit exceeded
9	Execution timed out	1088 ms	2812 KB	Time limit exceeded
10	Execution timed out	1080 ms	2936 KB	Time limit exceeded