제출 #1131163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131163		Gray	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	컴파일 에러	0 ms	0 KiB

sortbooks

#include <algorithm>
#include <bits/stdc++.h>

using namespace std;

#define ll int
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

// const ll INF = 2e18;
// const ll MOD = 1e9+7;

struct seg_tree{
    struct node{
        vector<ll> vals;
        ll res;
    };
    vector<node> t;
    ll sz, rsz;
    seg_tree(ll N){
        sz=N*4; rsz=N;
        t.resize(sz);
    }

    void build(ll tl, ll tr, ll v, vector<ll> &a){
        if (tl==tr){
            t[v].vals.push_back(a[tl]);
            t[v].res=0;
        }else{
            ll tm = (tl+tr)/2;
            build(tl, tm, v*2, a);
            build(tm+1, tr, v*2+1, a);
            // cout << "SYATY" << endl;
            assert(!(t[v*2].vals.empty() or t[v*2+1].vals.empty()));
            t[v].vals.resize(tr-tl+1);
            merge(t[v*2].vals.begin(), t[v*2].vals.end(), t[v*2+1].vals.begin(), t[v*2+1].vals.end(), t[v].vals.begin());
            // cout << "EDN" << endl;
            assert((ll)t[v].vals.size()==(tr-tl+1));
            t[v].res=max(t[v*2].res, t[v*2+1].res);
            ll ind = lower_bound(t[v*2+1].vals.begin(), t[v*2+1].vals.end(), t[v*2].vals.back())-t[v*2+1].vals.begin();
            t[v].res=max(t[v].res, (ind-1>=0?t[v*2+1].vals[ind-1]+t[v*2].vals.back():0ll));
        }
    }

    pair<ll, ll> query(ll tl, ll tr, ll v, ll l, ll r, ll pass_mx){
        // cout << tl << "-" << tr << ln;
        if (l>r) return {-INF, pass_mx};
        else if (tl==l and tr==r){
            // cout << tl << "-" << tr << "->" <<  t[v].res << ln;
            if (pass_mx==-INF) return {t[v].res, t[v].vals.back()};
            else{
                ll ind = lower_bound(t[v].vals.begin(), t[v].vals.end(), pass_mx)-t[v].vals.begin();
                ll res = max(t[v].res, (ind-1>=0?pass_mx+t[v].vals[ind-1]:0));
                // cout << tl << "-" << tr << " : " << ind << "->" << (ind-1>=0?pass_mx+t[v].vals[ind-1]:0) << ln;
                return {res, max(pass_mx, t[v].vals.back())};
            }
        }else{
            ll tm = (tl+tr)/2;
            pair<ll, ll> res1 = query(tl, tm, v*2, l, min(r, tm), pass_mx);
            pass_mx=res1.ss;
            pair<ll, ll> res2 = query(tm+1, tr, v*2+1, max(l, tm+1), r, pass_mx);
            return {max(res1.ff, res2.ff), res2.ss};
        }
    }

    void build(vector<ll> &a){
        build(0, rsz-1, 1, a);
    }

    ll query(ll l, ll r){
        // cout << "Start" << endl;
        ll res= query(0, rsz-1, 1, l, r, -INF).ff;
        // cout << "End" << endl;
        return res;
    }
};



void solve(){
    ll n, m; cin >> n >> m;
    vector<ll> a(n);
    for (ll i=0; i<n; i++) cin >> a[i];
    seg_tree tr(n);
    tr.build(a);
    // return;
    while (m--){
        ll l, r, k; cin >> l >> r >> k;
        l--; r--;
        ll res = tr.query(l, r);
        // cout << res << " -> ";
        if (res>k){
            cout << 0 << ln;
        }else{
            cout << 1 << ln;
        }
    }
}
/*
6 8 7 9 7.5

*/
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = chrono::high_resolution_clock::now();
    ll t=1;
    // cin >> t >> n;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

컴파일 시 표준 에러 (stderr) 메시지

sortbooks.cpp: In member function 'void seg_tree::build(int, int, int, std::vector<int>&)':
sortbooks.cpp:45:25: error: no matching function for call to 'max(int&, long long int)'
   45 |             t[v].res=max(t[v].res, (ind-1>=0?t[v*2+1].vals[ind-1]+t[v*2].vals.back():0ll));
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:61,
                 from sortbooks.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
sortbooks.cpp:45:25: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   45 |             t[v].res=max(t[v].res, (ind-1>=0?t[v*2+1].vals[ind-1]+t[v*2].vals.back():0ll));
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:61,
                 from sortbooks.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
sortbooks.cpp:45:25: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   45 |             t[v].res=max(t[v].res, (ind-1>=0?t[v*2+1].vals[ind-1]+t[v*2].vals.back():0ll));
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from sortbooks.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
sortbooks.cpp:45:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   45 |             t[v].res=max(t[v].res, (ind-1>=0?t[v*2+1].vals[ind-1]+t[v*2].vals.back():0ll));
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from sortbooks.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
sortbooks.cpp:45:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   45 |             t[v].res=max(t[v].res, (ind-1>=0?t[v*2+1].vals[ind-1]+t[v*2].vals.back():0ll));
      |                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp: In member function 'std::pair<int, int> seg_tree::query(int, int, int, int, int, int)':
sortbooks.cpp:51:27: error: 'INF' was not declared in this scope
   51 |         if (l>r) return {-INF, pass_mx};
      |                           ^~~
sortbooks.cpp:51:39: error: could not convert '{<expression error>, pass_mx}' from '<brace-enclosed initializer list>' to 'std::pair<int, int>'
   51 |         if (l>r) return {-INF, pass_mx};
      |                                       ^
      |                                       |
      |                                       <brace-enclosed initializer list>
sortbooks.cpp:54:27: error: 'INF' was not declared in this scope
   54 |             if (pass_mx==-INF) return {t[v].res, t[v].vals.back()};
      |                           ^~~
sortbooks.cpp: In member function 'int seg_tree::query(int, int)':
sortbooks.cpp:76:43: error: 'INF' was not declared in this scope
   76 |         ll res= query(0, rsz-1, 1, l, r, -INF).ff;
      |                                           ^~~