oj.uz

Submission #497507

# Submission time Handle Problem Language Result Execution time Memory
497507 2021-12-23T07:54:00 Z vinnipuh01 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 253 ms 262148 KB 
#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[ 4000001 ];

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

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 () {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 219432 KB Output is correct
2 Correct 103 ms 219384 KB Output is correct
3 Correct 106 ms 219512 KB Output is correct
4 Correct 102 ms 219464 KB Output is correct
5 Correct 99 ms 219496 KB Output is correct
6 Correct 101 ms 219712 KB Output is correct
7 Correct 107 ms 219684 KB Output is correct
8 Correct 105 ms 219720 KB Output is correct
9 Correct 99 ms 219480 KB Output is correct
10 Correct 98 ms 219464 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 219432 KB Output is correct
2 Correct 103 ms 219384 KB Output is correct
3 Correct 106 ms 219512 KB Output is correct
4 Correct 102 ms 219464 KB Output is correct
5 Correct 99 ms 219496 KB Output is correct
6 Correct 101 ms 219712 KB Output is correct
7 Correct 107 ms 219684 KB Output is correct
8 Correct 105 ms 219720 KB Output is correct
9 Correct 99 ms 219480 KB Output is correct
10 Correct 98 ms 219464 KB Output is correct
11 Correct 104 ms 220272 KB Output is correct
12 Correct 113 ms 222656 KB Output is correct
13 Correct 113 ms 222592 KB Output is correct
14 Correct 110 ms 222756 KB Output is correct
15 Correct 112 ms 222732 KB Output is correct
16 Correct 112 ms 222652 KB Output is correct
17 Correct 109 ms 222116 KB Output is correct
18 Correct 107 ms 219984 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 253 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 183 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 219432 KB Output is correct
2 Correct 103 ms 219384 KB Output is correct
3 Correct 106 ms 219512 KB Output is correct
4 Correct 102 ms 219464 KB Output is correct
5 Correct 99 ms 219496 KB Output is correct
6 Correct 101 ms 219712 KB Output is correct
7 Correct 107 ms 219684 KB Output is correct
8 Correct 105 ms 219720 KB Output is correct
9 Correct 99 ms 219480 KB Output is correct
10 Correct 98 ms 219464 KB Output is correct
11 Correct 104 ms 220272 KB Output is correct
12 Correct 113 ms 222656 KB Output is correct
13 Correct 113 ms 222592 KB Output is correct
14 Correct 110 ms 222756 KB Output is correct
15 Correct 112 ms 222732 KB Output is correct
16 Correct 112 ms 222652 KB Output is correct
17 Correct 109 ms 222116 KB Output is correct
18 Correct 107 ms 219984 KB Output is correct
19 Runtime error 191 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 219432 KB Output is correct
2 Correct 103 ms 219384 KB Output is correct
3 Correct 106 ms 219512 KB Output is correct
4 Correct 102 ms 219464 KB Output is correct
5 Correct 99 ms 219496 KB Output is correct
6 Correct 101 ms 219712 KB Output is correct
7 Correct 107 ms 219684 KB Output is correct
8 Correct 105 ms 219720 KB Output is correct
9 Correct 99 ms 219480 KB Output is correct
10 Correct 98 ms 219464 KB Output is correct
11 Correct 104 ms 220272 KB Output is correct
12 Correct 113 ms 222656 KB Output is correct
13 Correct 113 ms 222592 KB Output is correct
14 Correct 110 ms 222756 KB Output is correct
15 Correct 112 ms 222732 KB Output is correct
16 Correct 112 ms 222652 KB Output is correct
17 Correct 109 ms 222116 KB Output is correct
18 Correct 107 ms 219984 KB Output is correct
19 Runtime error 253 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -