oj.uz

Submission #497506

# Submission time Handle Problem Language Result Execution time Memory
497506 2021-12-23T07:53:45 Z vinnipuh01 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 476 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[ 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

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 80 ms 164636 KB Output is correct
2 Correct 78 ms 164676 KB Output is correct
3 Correct 89 ms 164672 KB Output is correct
4 Correct 86 ms 164664 KB Output is correct
5 Correct 81 ms 164648 KB Output is correct
6 Correct 80 ms 164912 KB Output is correct
7 Correct 82 ms 164892 KB Output is correct
8 Correct 82 ms 164820 KB Output is correct
9 Correct 86 ms 164800 KB Output is correct
10 Correct 83 ms 164708 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 164636 KB Output is correct
2 Correct 78 ms 164676 KB Output is correct
3 Correct 89 ms 164672 KB Output is correct
4 Correct 86 ms 164664 KB Output is correct
5 Correct 81 ms 164648 KB Output is correct
6 Correct 80 ms 164912 KB Output is correct
7 Correct 82 ms 164892 KB Output is correct
8 Correct 82 ms 164820 KB Output is correct
9 Correct 86 ms 164800 KB Output is correct
10 Correct 83 ms 164708 KB Output is correct
11 Correct 83 ms 165460 KB Output is correct
12 Correct 90 ms 167780 KB Output is correct
13 Correct 99 ms 167856 KB Output is correct
14 Correct 106 ms 168108 KB Output is correct
15 Correct 91 ms 167876 KB Output is correct
16 Correct 89 ms 167892 KB Output is correct
17 Correct 95 ms 167248 KB Output is correct
18 Correct 85 ms 165184 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 354 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 217668 KB Output is correct
2 Correct 407 ms 217692 KB Output is correct
3 Correct 206 ms 175376 KB Output is correct
4 Correct 203 ms 175348 KB Output is correct
5 Correct 208 ms 175408 KB Output is correct
6 Correct 165 ms 175332 KB Output is correct
7 Correct 171 ms 175348 KB Output is correct
8 Correct 185 ms 174964 KB Output is correct
9 Correct 117 ms 165104 KB Output is correct
10 Correct 181 ms 174624 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 164636 KB Output is correct
2 Correct 78 ms 164676 KB Output is correct
3 Correct 89 ms 164672 KB Output is correct
4 Correct 86 ms 164664 KB Output is correct
5 Correct 81 ms 164648 KB Output is correct
6 Correct 80 ms 164912 KB Output is correct
7 Correct 82 ms 164892 KB Output is correct
8 Correct 82 ms 164820 KB Output is correct
9 Correct 86 ms 164800 KB Output is correct
10 Correct 83 ms 164708 KB Output is correct
11 Correct 83 ms 165460 KB Output is correct
12 Correct 90 ms 167780 KB Output is correct
13 Correct 99 ms 167856 KB Output is correct
14 Correct 106 ms 168108 KB Output is correct
15 Correct 91 ms 167876 KB Output is correct
16 Correct 89 ms 167892 KB Output is correct
17 Correct 95 ms 167248 KB Output is correct
18 Correct 85 ms 165184 KB Output is correct
19 Runtime error 285 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 80 ms 164636 KB Output is correct
2 Correct 78 ms 164676 KB Output is correct
3 Correct 89 ms 164672 KB Output is correct
4 Correct 86 ms 164664 KB Output is correct
5 Correct 81 ms 164648 KB Output is correct
6 Correct 80 ms 164912 KB Output is correct
7 Correct 82 ms 164892 KB Output is correct
8 Correct 82 ms 164820 KB Output is correct
9 Correct 86 ms 164800 KB Output is correct
10 Correct 83 ms 164708 KB Output is correct
11 Correct 83 ms 165460 KB Output is correct
12 Correct 90 ms 167780 KB Output is correct
13 Correct 99 ms 167856 KB Output is correct
14 Correct 106 ms 168108 KB Output is correct
15 Correct 91 ms 167876 KB Output is correct
16 Correct 89 ms 167892 KB Output is correct
17 Correct 95 ms 167248 KB Output is correct
18 Correct 85 ms 165184 KB Output is correct
19 Runtime error 354 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -