oj.uz

Submission #502731

# Submission time Handle Problem Language Result Execution time Memory
502731 2022-01-06T14:08:43 Z nickmet2004 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++11
0 / 100
 595 ms 262148 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+5;
int n , q , a[N];
struct Node{
    int mx ,ans;
    set<int> s;
};
Node T[4*N];

void B(int l , int r, int pos , vector<int> y){
    for(int x : y)T[pos].s.insert(x), T[pos].mx = max(T[pos].mx , x);
    if(l==r)return;
    int mid = (l + r) >> 1;
    vector<int> ax , bx;
    for(int i = 0; i <= mid; ++i)ax.emplace_back(y[i]);
    for(int i =mid + 1; i <= y.size(); ++i) bx.emplace_back(y[i]);
    B(l ,mid , pos * 2 , ax); B( mid + 1 , r , pos * 2 + 1 , bx);
    int MX = T[pos * 2].mx;
    auto it = T[pos*2 + 1].s.lower_bound(MX);
    if(it != T[pos*2 + 1].s.begin()){
        --it;
        T[pos].ans = MX + *it;
    }
    T[pos].ans = max({T[pos].ans , T[pos * 2].ans , T[pos * 2 + 1].ans});
    return;
}
vector<int> H;
void y(int L , int R , int l=1 , int r=n , int pos=1){
    if(r < L || R < l)return;
    if(L <= l && r <= R) {H.push_back(pos); return;}
    int mid = (l + r) >> 1;
    y(L , R , l , mid , pos * 2); y(L , R , mid +1 ,r ,pos * 2 + 1);
}

int main (){
    ios_base::sync_with_stdio(0);
    cin >> n>>q;
    vector<int> K;
    for(int i = 1; i<= n; ++i)cin >> a[i] , K.emplace_back(a[i]);
    B(1 , n , 1 , K);
    while(q--){
        int l , r ,d;
        cin >> l >> r >> d;
        H.clear();
        y(l , r);
        int z = 0;
        sort(H.begin() , H.end());
        for(int i = 0; i< H.size(); ++i){
            //cout << H[i] << " pos" << endl;
            z = max(z , T[H[i]].ans);
            for(int j = i + 1; j < H.size(); ++j){
                int MX = T[H[i]].mx;
                auto it = T[H[j]].s.lower_bound(MX);
                if(it != T[H[j]].s.begin()){
                    --it;
                    z = max(z , MX + *it);
                }
            }
        }
        //cout << z << " z"<<endl;
        if(z > d)cout << 0 << endl;
        else cout << 1 << endl;
    }

}

Compilation message

sortbooks.cpp: In function 'void B(int, int, int, std::vector<int>)':
sortbooks.cpp:18:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i =mid + 1; i <= y.size(); ++i) bx.emplace_back(y[i]);
      |                         ~~^~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:50:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int i = 0; i< H.size(); ++i){
      |                        ~^~~~~~~~~~
sortbooks.cpp:53:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for(int j = i + 1; j < H.size(); ++j){
      |                                ~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 219460 KB Output is correct
2 Correct 95 ms 219636 KB Output is correct
3 Runtime error 297 ms 262144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 219460 KB Output is correct
2 Correct 95 ms 219636 KB Output is correct
3 Runtime error 297 ms 262144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 595 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 338 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 219460 KB Output is correct
2 Correct 95 ms 219636 KB Output is correct
3 Runtime error 297 ms 262144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 219460 KB Output is correct
2 Correct 95 ms 219636 KB Output is correct
3 Runtime error 297 ms 262144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -