Submission #259618

#	Time	Username	Problem	Language	Result	Execution time	Memory
259618		dantoh000	Santa Claus (RMI19_santa)	C++14	20 / 100	1095 ms	760 KiB

santa

#include <bits/stdc++.h>
using namespace std;
int n;
int x[6000], h[6000], v[6000];
bool test(int l, int r){
    multiset<int> ms;
    for (int i = 0; i < l; i++){
        if (h[i]){
            auto it = ms.lower_bound(v[i]);
            if (it != ms.end()) ms.erase(it);
        }
        else{
            ms.insert(v[i]);
        }
    }
    for (int i = l; i <= r; i++){
        if (h[i] == 0) ms.insert(v[i]);
    }
    for (int i = l; i <= r; i++){
        if (h[i] == 1){
            auto it = ms.lower_bound(v[i]);
            if (it != ms.end()) ms.erase(it);
        }
    }
    return ms.empty();
}
int main(){
    int tc;
    scanf("%d",&tc);
    while (tc--){
        scanf("%d",&n);
        int lastelf = 0;
        for (int i = 0; i < n; i++){
            scanf("%d",&x[i]);
        }
        for (int i = 0; i < n; i++){
            scanf("%d",&h[i]);
            if (h[i] == 0) lastelf = i;
        }
        for (int i = 0; i < n; i++){
            scanf("%d",&v[i]);
        }
        for (int i = 0; i < n; i++){
            if (i < lastelf){
                printf("-1 ");
                continue;
            }
            int lo = 0, hi = i;
            while (lo < hi){
                int mid = (lo+hi+1)/2;
                if (test(mid,i)){
                    lo = mid;
                }
                else hi = mid-1;
            }
            if (test(lo,i)){
                printf("%d ",2*x[i]-x[lo]);
            }
            else printf("-1 ");
        }
        printf("\n");
    }

}

Compilation message (stderr)

santa.cpp: In function 'int main()':
santa.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&tc);
     ~~~~~^~~~~~~~~~
santa.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&n);
         ~~~~~^~~~~~~~~
santa.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&x[i]);
             ~~~~~^~~~~~~~~~~~
santa.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&h[i]);
             ~~~~~^~~~~~~~~~~~
santa.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&v[i]);
             ~~~~~^~~~~~~~~~~~

• Subtask 1: 20 / 100