oj.uz

Submission #259618

# Submission time Handle Problem Language Result Execution time Memory
259618 2020-08-08T04:36:18 Z dantoh000 Santa Claus (RMI19_santa) C++14
20 / 100
 1000 ms 760 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 19 ms 384 KB Output is correct
3 Execution timed out 1091 ms 504 KB Time limit exceeded
4 Execution timed out 1085 ms 504 KB Time limit exceeded
5 Execution timed out 1095 ms 512 KB Time limit exceeded
6 Execution timed out 1086 ms 760 KB Time limit exceeded
7 Execution timed out 400 ms 384 KB Time limit exceeded (wall clock)
8 Execution timed out 389 ms 504 KB Time limit exceeded (wall clock)
9 Execution timed out 425 ms 384 KB Time limit exceeded (wall clock)
10 Execution timed out 397 ms 384 KB Time limit exceeded (wall clock)