Submission #497504

#TimeUsernameProblemLanguageResultExecution timeMemory
497504vinnipuh01Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
34 / 100
544 ms262148 KiB
#include <iostream> #include <bits/stdc++.h> #include <cmath> #include <algorithm> #include <vector> #include <deque> #include <set> #include <stack> #include <string> #include <map> #include <queue> using namespace std; const long long oo = 1000000000000000000; long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos; /* ViHHiPuh (( `'-""``""-'` )) )-__-_.._-__-( / --- (o _ o) --- \ \ .-* ( .0. ) *-. / _'-. ,_ '=' _, .-'_ / `;#'#'# - #'#'#;` \ \_)) -----'#'----- ((_/ # --------- # '# ------- ------ #' /..-'# ------- #'-.\ _\...-\'# -- #'/-.../_ ((____)- '#' -(____)) cout << fixed << setprecision(6) << x; freopen ( "sum.in", "r", stdin ) */ struct Node { set <int> v; int ans; public : Node operator + ( Node a ) { Node c; c.ans = max( ans, a.ans ); int l, r; l = r = 0; int mx = *v.rbegin(); if ( *a.v.begin() < mx ) { auto it = a.v.lower_bound( mx ); it = --it; c.ans = max( c.ans, *it + mx ); } c.v = v; for ( auto i : a.v ) c.v.insert( i ); return c; } } t[ 3000001 ]; struct Node1 { int ans, mx; } an; int n, m, a[ 1000001 ]; void build( int v, int tl, int tr ) { if ( tl == tr ) { t[ v ].v.insert( a[ tl ] ); t[ v ].ans = 0; return; } int mid = ( tl + tr ) / 2; build( v + v, tl, mid ); build( v + v + 1, mid + 1, tr ); t[ v ] = t[ v + v ] + t[ v + v + 1 ]; } void gett( int v, int tl, int tr, int l, int r ) { if ( tl > r || tr < l ) return; if ( tl >= l && tr <= r ) { an.ans = max( an.ans, t[ v ].ans ); if ( an.mx > *t[ v ].v.begin() ) { auto it = t[ v ].v.lower_bound( an.mx ); it = --it; an.ans = max( an.ans, an.mx + *it ); } an.mx = max( an.mx, *t[ v ].v.rbegin() ); return; } int mid = ( tl + tr ) / 2; gett( v + v, tl, mid, l, r ); gett( v + v + 1, mid + 1, tr, l, r ); } main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for ( int i = 1; i <= n; i ++ ) { cin >> a[ i ]; } int l, r, x; build( 1, 1, n ); while ( m -- ) { cin >> l >> r >> x; num = 0; an.mx = 0; an.ans = 0; gett( 1, 1, n, l, r ); cout << ( x >= an.ans ) << "\n"; } } /* 9 1 10 6 7 10 1 3 7 3 7 2 3 1 3 1 7 1 9 1 3 8 */

Compilation message (stderr)

sortbooks.cpp: In member function 'Node Node::operator+(Node)':
sortbooks.cpp:50:8: warning: variable 'l' set but not used [-Wunused-but-set-variable]
   50 |    int l, r;
      |        ^
sortbooks.cpp: At global scope:
sortbooks.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main () {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...