Submission #890637

#	Time	Username	Problem	Language	Result	Execution time	Memory
890637		NotLinux	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	404 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define mid (l+r) >> 1
const int inf = 1e9 + 7;
struct node {
    int answer;
    vector < int > v;
    int smaller(int x){
        auto it = (lower_bound(v.begin(),v.end(),x));
        if(it == v.begin() or v.size() == 0)return -inf;
        else return *(--it);
    }
};
node merge(node a , node b){
        node product;
        product.answer = max({a.answer , b.answer , a.smaller(1e18) + b.smaller(a.smaller(1e18))});
        int itr1 = 0 , itr2 = 0;
        while(itr1 < a.v.size() or itr2 < b.v.size()){
            if(itr1 == a.v.size()){
                product.v.push_back(b.v[itr2]);
                itr2++;
            }
            else if(itr2 == b.v.size()){
                product.v.push_back(a.v[itr1]);
                itr1++;
            }
            else{
                if(a.v[itr1] < b.v[itr2]){
                    product.v.push_back(a.v[itr1]);
                    itr1++;
                }
                else{
                    product.v.push_back(b.v[itr2]);
                    itr2++;
                }
            }
        }
        return product;
}
node etkisiz;
struct SEGMENT_TREE {
    vector < node > tree;
    int sz;
    void init(int x){
        sz = x;
        tree.clear();tree.resize(4*x);
    }
    node _query(int ind , int l , int r , int ql , int qr){
        if(l >= ql and r <= qr)return tree[ind];
        else if(l > qr or r < ql)return etkisiz;
        return merge(_query(ind*2,l,mid,ql,qr) , _query(ind*2+1,mid+1,r,ql,qr));
    }
    int query(int l , int r){
        return _query(1,1,sz,l,r).answer;
    }
    void _update(int ind , int l, int r , int pos , int val){
        if(l == r){
            tree[ind].answer = 0;
            tree[ind].v = {val};
            return;
        }
        if(pos <= mid)_update(ind*2,l,mid,pos,val);
        else _update(ind*2+1,mid+1,r,pos,val);
        tree[ind] = merge(tree[ind*2],tree[ind*2+1]);
    }
    void update(int pos , int val){
        _update(1,1,sz,pos,val);
    }
};
signed main(){
    etkisiz.answer = 0;
    etkisiz.v = {};
    int n,m;cin >> n >> m;
    vector < int > arr(n);
    for(auto &inp : arr)cin >> inp;
    SEGMENT_TREE segt;
    segt.init(n);
    for(int i = 1;i<=n;i++){
        segt.update(i,arr[i-1]);
    }
    while(m--){
        int cl,cr,cw;cin >> cl >> cr >> cw;
        cout << ( segt.query(cl,cr) > cw ? 0 : 1 ) << '\n';
    }
}

Compilation message (stderr)

sortbooks.cpp: In function 'node merge(node, node)':
sortbooks.cpp:16:63: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 |         product.answer = max({a.answer , b.answer , a.smaller(1e18) + b.smaller(a.smaller(1e18))});
      |                                                               ^~~~
sortbooks.cpp:16:91: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 |         product.answer = max({a.answer , b.answer , a.smaller(1e18) + b.smaller(a.smaller(1e18))});
      |                                                                                           ^~~~
sortbooks.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         while(itr1 < a.v.size() or itr2 < b.v.size()){
      |               ~~~~~^~~~~~~~~~~~
sortbooks.cpp:18:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         while(itr1 < a.v.size() or itr2 < b.v.size()){
      |                                    ~~~~~^~~~~~~~~~~~
sortbooks.cpp:19:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |             if(itr1 == a.v.size()){
      |                ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             else if(itr2 == b.v.size()){
      |                     ~~~~~^~~~~~~~~~~~~
sortbooks.cpp: In member function 'node SEGMENT_TREE::_query(int, int, int, int, int)':
sortbooks.cpp:51:68: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         return merge(_query(ind*2,l,mid,ql,qr) , _query(ind*2+1,mid+1,r,ql,qr));
      |                                                                    ^
sortbooks.cpp: In member function 'void SEGMENT_TREE::_update(int, int, int, int, int)':
sortbooks.cpp:63:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         else _update(ind*2+1,mid+1,r,pos,val);
      |                                 ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23