답안 #152627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152627	2019-09-08T15:58:29 Z	andrew	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	컴파일 오류	0 ms	0 KB

sortbooks

SUBMISSION #147752
#	Submission timeUTC+3	Handle	Problem	Language	Result	Execution time	Memory
147752	2019-08-30 17:38:49	andrew	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	
100 / 100
1723 ms	152308 KB
sortbooks
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)
 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T> void vout(T s){cout << s << endl;exit(0);}
 
ll ans[MAXN];
 
vector <ll> v[MAXN];
 
struct qry{
    ll l, r, idx, k;
};
 
bool cmp(qry a, qry b){
    if(a.l > b.l)return 1;
    if(a.l < b.l)return 0;
    return (a.idx < b.idx);
}
 
ll t[4 * MAXN];
 
void modify(ll v, ll tl, ll tr, ll pos, ll val){
    if(tl == tr)t[v] = val; else{
        ll tm = (tl + tr) >> 1;
        if(pos <= tm)modify(v << 1, tl, tm, pos, val);
        else modify((v << 1) + 1, tm + 1, tr, pos, val);
        t[v] = max(t[v << 1], t[(v << 1) + 1]);
    }
}
 
ll get(ll v, ll tl, ll tr, ll l, ll r){
    if(l > r)return 0;
    if(tl == l && tr == r)return t[v];
    ll tm = (tl + tr) >> 1;
    return max(get(v << 1, tl, tm, l, min(r, tm)), get((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r));
}
 
int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
 
    ll n, m;
    cin >> n >> m;
 
    vector <ll> w(n + 1), le(n + 1);
 
    for(int i = 1; i <= n; i++)cin >> w[i];
 
    w[0] = 1e18;
 
    vector <ll> st;
    st.p_b(0);
 
    for(int i = 1; i <= n; i++){
        while(w[st.back()] <= w[i])st.pop_back();
        le[i] = st.back();
        v[le[i]].p_b(i);
        st.p_b(i);
    }
 
    vector <qry> c(m);
 
    ll uk = n;
 
    for(int i = 0; i < m; i++){
        cin >> c[i].l >> c[i].r >> c[i].k;
        c[i].idx = i;
    }
 
    sort(all(c), cmp);
 
    for(auto kek : c){
        while(kek.l < uk){
            for(auto j : v[uk - 1]){
                modify(1, 1, n, j, w[uk - 1] + w[j]);
            }
            uk--;
        }
        ans[kek.idx] = (get(1, 1, n, kek.l, kek.r) <= kek.k);
    }
 
    for(int i = 0; i < m; i++)cout << ans[i] << "\n";
 
    return 0;
}

Compilation message

sortbooks.cpp:2:12: error: stray '#' in program
 SUBMISSION #147752
            ^
sortbooks.cpp:3:3: error: invalid preprocessing directive #Submission
 # Submission timeUTC+3 Handle Problem Language Result Execution time Memory
   ^~~~~~~~~~
sortbooks.cpp:4:13: error: invalid digit "8" in octal constant
 147752 2019-08-30 17:38:49 andrew Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17 
             ^~
sortbooks.cpp:2:1: error: 'SUBMISSION' does not name a type
 SUBMISSION #147752
 ^~~~~~~~~~
In file included from /usr/include/c++/7/cmath:43:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/ext/type_traits.h:162:35: error: 'bool __gnu_cxx::__is_null_pointer' redeclared as different kind of symbol
   __is_null_pointer(std::nullptr_t)
                                   ^
/usr/include/c++/7/ext/type_traits.h:157:5: note: previous declaration 'template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)'
     __is_null_pointer(_Type)
     ^~~~~~~~~~~~~~~~~
/usr/include/c++/7/ext/type_traits.h:162:26: error: 'nullptr_t' is not a member of 'std'
   __is_null_pointer(std::nullptr_t)
                          ^~~~~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/stl_pair.h:59,
                 from /usr/include/c++/7/bits/stl_algobase.h:64,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/type_traits:362:26: error: 'std::size_t' has not been declared
   template<typename _Tp, std::size_t _Size>
                          ^~~
/usr/include/c++/7/type_traits:363:25: error: '_Size' was not declared in this scope
     struct is_array<_Tp[_Size]>
                         ^~~~~
/usr/include/c++/7/type_traits:363:31: error: template argument 1 is invalid
     struct is_array<_Tp[_Size]>
                               ^
/usr/include/c++/7/type_traits:561:42: error: 'nullptr_t' is not a member of 'std'
     struct __is_null_pointer_helper<std::nullptr_t>
                                          ^~~~~~~~~
/usr/include/c++/7/type_traits:561:51: error: template argument 1 is invalid
     struct __is_null_pointer_helper<std::nullptr_t>
                                                   ^
/usr/include/c++/7/type_traits:1464:37: error: 'size_t' is not a member of 'std'
     : public integral_constant<std::size_t, __alignof__(_Tp)> { };
                                     ^~~~~~
/usr/include/c++/7/type_traits:1464:37: note: suggested alternative:
In file included from /usr/include/stdlib.h:32:0,
                 from /usr/include/c++/7/bits/std_abs.h:38,
                 from /usr/include/c++/7/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/7/include/stddef.h:216:23: note:   'size_t'
 typedef __SIZE_TYPE__ size_t;
                       ^~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/stl_pair.h:59,
                 from /usr/include/c++/7/bits/stl_algobase.h:64,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/type_traits:1464:61: error: template argument 1 is invalid
     : public integral_constant<std::size_t, __alignof__(_Tp)> { };
                                                             ^
/usr/include/c++/7/type_traits:1464:61: note: invalid template non-type parameter
/usr/include/c++/7/type_traits:1469:37: error: 'size_t' is not a member of 'std'
     : public integral_constant<std::size_t, 0> { };
                                     ^~~~~~
/usr/include/c++/7/type_traits:1469:37: note: suggested alternative:
In file included from /usr/include/stdlib.h:32:0,
                 from /usr/include/c++/7/bits/std_abs.h:38,
                 from /usr/include/c++/7/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/7/include/stddef.h:216:23: note:   'size_t'
 typedef __SIZE_TYPE__ size_t;
                       ^~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/stl_pair.h:59,
                 from /usr/include/c++/7/bits/stl_algobase.h:64,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/type_traits:1469:46: error: template argument 1 is invalid
     : public integral_constant<std::size_t, 0> { };
                                              ^
/usr/include/c++/7/type_traits:1469:46: note: invalid template non-type parameter
/usr/include/c++/7/type_traits:1471:26: error: 'std::size_t' has not been declared
   template<typename _Tp, std::size_t _Size>
                          ^~~
/usr/include/c++/7/type_traits:1472:21: error: '_Size' was not declared in this scope
     struct rank<_Tp[_Size]>
                     ^~~~~
/usr/include/c++/7/type_traits:1472:27: error: template argument 1 is invalid
     struct rank<_Tp[_Size]>
                           ^
/usr/include/c++/7/type_traits:1473:37: error: 'size_t' is not a member of 'std'
     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
                                     ^~~~~~
/usr/include/c++/7/type_traits:1473:37: note: suggested alternative:
In file included from /usr/include/stdlib.h:32:0,
                 from /usr/include/c++/7/bits/std_abs.h:38,
                 from /usr/include/c++/7/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/7/include/stddef.h:216:23: note:   'size_t'
 typedef __SIZE_TYPE__ size_t;
                       ^~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/stl_pair.h:59,
                 from /usr/include/c++/7/bits/stl_algobase.h:64,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/type_traits:1473:65: error: template argument 1 is invalid
     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
                                                                 ^
/usr/include/c++/7/type_traits:1473:65: note: invalid template non-type parameter
/usr/include/c++/7/type_traits:1477:37: error: 'size_t' is not a member of 'std'
     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
                                     ^~~~~~
/usr/include/c++/7/type_traits:1477:37: note: suggested alternative:
In file included from /usr/include/stdlib.h:32:0,
                 from /usr/include/c++/7/bits/std_abs.h:38,
                 from /usr/include/c++/7/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/7/include/stddef.h:216:23: note:   'size_t'
 typedef __SIZE_TYPE__ size_t;
                       ^~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/stl_pair.h:59,
                 from /usr/include/c++/7/bits/stl_algobase.h:64,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/type_traits:1477:65: error: template argument 1 is invalid
     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
                                                                 ^
/usr/include/c++/7/type_traits:1477:65: note: invalid template non-type parameter
/usr/include/c++/7/type_traits:1482:37: error: 'size_t' is not a member of 'std'
     : public integral_constant<std::size_t, 0> { };
                                     ^~~~~~
/usr/include/c++/7/type_traits:1482:37: note: suggested alternative:
In file included from /usr/include/stdlib.h:32:0,
                 from /usr/include/c++/7/bits/std_abs.h:38,
                 from /usr/include/c++/7/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/7/include/stddef.h:216:23: note:   'size_t'
 typedef __SIZE_TYPE__ size_t;
                       ^~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/stl_pair.h:59,
                 from /usr/include/c++/7/bits/stl_algobase.h:64,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/type_traits:1482:46: error: template argument 1 is invalid
     : public integral_constant<std::size_t, 0> { };
                                              ^
/usr/include/c++/7/type_traits:1482:46: note: invalid template non-type parameter
/usr/include/c++/7/type_traits:1484:42: error: 'std::size_t' has not been declared
   template<typename _Tp, unsigned _Uint, std::size_t _Size>
                                          ^~~
/usr/include/c++/7/type_traits:1485:23: error: '_Size' was not declared in this scope
     struct extent<_Tp[_Size], _Uint>
                       ^~~~~
/usr/include/c++/7/type_traits:1485:36: error: template argument 1 is invalid
     struct extent<_Tp[_Size], _Uint>
                                    ^
/usr/include/c++/7/type_traits:1486:37: error: 'size_t' is not a member of 'std'
     : public integral_constant<std::size_t,
                                     ^~~~~~
/usr/include/c++/7/type_traits:1486:37: note: suggested alternative:
In file included from /usr/include/stdlib.h:32:0,
                 from /usr/include/c++/7/bits/std_abs.h:38,
                 from /usr/include/c++/7/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/7/include/stddef.h:216:23: note:   'size_t'
 typedef __SIZE_TYPE__ size_t;
                       ^~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/stl_pair.h:59,
                 from /usr/include/c++/7/bits/stl_algobase.h:64,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/type_traits:1487:24: error: '_Size' was not declared in this scope
           _Uint == 0 ? _Size : extent<_Tp,
                        ^~~~~
/usr/include/c++/7/type_traits:1488:28: error: template argument 1 is invalid
           _Uint - 1>::value>
                            ^
/usr/include/c++/7/type_traits:1488:28: note: invalid template non-type parameter
/usr/include/c++/7/type_traits:1493:37: error: 'size_t' is not a member of 'std'
     : public integral_constant<std::size_t,
                                     ^~~~~~
/usr/include/c++/7/type_traits:1493:37: note: suggested alternative:
In file included from /usr/include/stdlib.h:32:0,
                 from /usr/include/c++/7/bits/std_abs.h:38,
                 from /usr/include/c++/7/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/7/include/stddef.h:216:23: note:   'size_t'
 typedef __SIZE_TYPE__ size_t;
                       ^~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/stl_pair.h:59,
                 from /usr/include/c++/7/bits/stl_algobase.h:64,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/type_traits:1495:31: error: template argument 1 is invalid
              _Uint - 1>::value>
                               ^
/usr/include/c++/7/type_traits:1495:31: note: invalid template non-type parameter
/usr/include/c++/7/type_traits:1944:26: error: 'std::size_t' has not been declared
   template<typename _Tp, std::size_t _Size>
                          ^~~
/usr/include/c++/7/type_traits:1945:30: error: '_Size' was not declared in this scope
     struct remove_extent<_Tp[_Size]>
                              ^~~~~
/usr/include/c++/7/type_traits:1945:36: error: template argument 1 is invalid
     struct remove_extent<_Tp[_Size]>
                                    ^
/usr/include/c++/7/type_traits:1957:26: error: 'std::size_t' has not been declared
   template<typename _Tp, std::size_t _Size>
                          ^~~
/usr/include/c++/7/type_traits:1958:35: error: '_Size' was not declared in this scope
     struct remove_all_extents<_Tp[_Size]>
                                   ^~~~~
/usr/include/c++/7/type_traits:1958:41: error: template argument 1 is invalid
     struct remove_all_extents<_Tp[_Size]>
                                         ^
/usr/include/c++/7/type_traits:2016:12: error: 'std::size_t' has not been declared
   template<std::size_t _Len>
            ^~~
/usr/include/c++/7/type_traits:2021:23: error: '_Len' was not declared in this scope
  unsigned char __data[_Len];
                       ^~~~
/usr/include/c++/7/type_traits:2021:23: note: suggested alternative: '__yn'
  unsigned char __data[_Len];
                       ^~~~
                       __yn
/usr/include/c++/7/type_traits:2036:12: error: 'std::size_t' has not been declared
   template<std::size_t _Len, std::size_t _Align =
            ^~~
/usr/include/c++/7/type_traits:2036:30: error: 'std::size_t' has not been declared
   template<std::size_t _Len, std::size_t _Align =
                              ^~~
/usr/include/c++/7/type_traits:2037:48: error: '_Len' was not declared in this scope
     __alignof__(typename __aligned_storage_msa<_Len>::__type)>
                                                ^~~~
/usr/include/c++/7/type_traits:2037:48: note: suggested alternative: '__yn'
     __alignof__(typename __aligned_storage_msa<_Len>::__type)>
                                                ^~~~
                                                __yn
/usr/include/c++/7/type_traits:2037:52: error: template argument 1 is invalid
     __alignof__(typename __aligned_storage_msa<_Len>::__type)>
                                                    ^
/usr/include/c++/7/type_traits:2042:23: error: '_Len' was not declared in this scope
  unsigned char __data[_Len];
                       ^~~~
/usr/include/c++/7/type_traits:2042:23: note: suggested alternative: '__yn'
  unsigned char __data[_Len];
                       ^~~~
                       __yn
/usr/include/c++/7/type_traits:2043:37: error: '_Align' was not declared in this scope
  struct __attribute__((__aligned__((_Align)))) { } __align;
                                     ^~~~~~
/usr/include/c++/7/type_traits:2043:37: note: suggested alternative: '__logl'
  struct __attribute__((__aligned__((_Align)))) { } __align;
                                     ^~~~~~
                                     __logl
In file included from /usr/include/c++/7/bits/stl_algobase.h:64:0,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/bits/stl_pair.h:86:12: error: 'std::size_t' has not been declared
   template<std::size_t...>
            ^~~
/usr/include/c++/7/bits/stl_pair.h:429:36: error: 'std::size_t' has not been declared
       template<typename... _Args1, std::size_t... _Indexes1,
                                    ^~~
/usr/include/c++/7/bits/stl_pair.h:430:36: error: 'std::size_t' has not been declared
                typename... _Args2, std::size_t... _Indexes2>
                                    ^~~
/usr/include/c++/7/bits/stl_pair.h:432:27: error: '_Indexes1' was not declared in this scope
              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
                           ^~~~~~~~~
/usr/include/c++/7/bits/stl_pair.h:432:36: error: expected parameter pack before '...'
              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
                                    ^~~
/usr/include/c++/7/bits/stl_pair.h:432:39: error: template argument 1 is invalid
              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
                                       ^
/usr/include/c++/7/bits/stl_pair.h:432:55: error: '_Indexes2' was not declared in this scope
              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
                                                       ^~~~~~~~~
/usr/include/c++/7/bits/stl_pair.h:432:64: error: expected parameter pack before '...'
              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
                                                                ^~~
/usr/include/c++/7/bits/stl_pair.h:432:67: error: template argument 1 is invalid
              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
                                                                   ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:65:0,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/bits/stl_iterator_base_types.h:116:67: error: 'ptrdiff_t' does not name a type
   template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
                                                                   ^~~~~~~~~
/usr/include/c++/7/bits/stl_iterator_base_types.h:182:15: error: 'ptrdiff_t' does not name a type
       typedef ptrdiff_t                   difference_type;
               ^~~~~~~~~
/usr/include/c++/7/bits/stl_iterator_base_types.h:193:15: error: 'ptrdiff_t' does not name a type
       typedef ptrdiff_t                   difference_type;
               ^~~~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from sortbooks.cpp:8:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:110:5: error: 'ptrdiff_t' does not name a type
     ptrdiff_t