oj.uz

Submission #497504

# Submission time Handle Problem Language Result Execution time Memory
497504 2021-12-23T07:53:20 Z vinnipuh01 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 544 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 85 ms 164680 KB Output is correct
2 Correct 87 ms 164580 KB Output is correct
3 Correct 87 ms 164684 KB Output is correct
4 Correct 79 ms 164588 KB Output is correct
5 Correct 82 ms 164676 KB Output is correct
6 Correct 91 ms 164900 KB Output is correct
7 Correct 98 ms 164868 KB Output is correct
8 Correct 74 ms 164804 KB Output is correct
9 Correct 74 ms 164716 KB Output is correct
10 Correct 76 ms 164676 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 164680 KB Output is correct
2 Correct 87 ms 164580 KB Output is correct
3 Correct 87 ms 164684 KB Output is correct
4 Correct 79 ms 164588 KB Output is correct
5 Correct 82 ms 164676 KB Output is correct
6 Correct 91 ms 164900 KB Output is correct
7 Correct 98 ms 164868 KB Output is correct
8 Correct 74 ms 164804 KB Output is correct
9 Correct 74 ms 164716 KB Output is correct
10 Correct 76 ms 164676 KB Output is correct
11 Correct 79 ms 165508 KB Output is correct
12 Correct 92 ms 167784 KB Output is correct
13 Correct 91 ms 167836 KB Output is correct
14 Correct 84 ms 167944 KB Output is correct
15 Correct 81 ms 167948 KB Output is correct
16 Correct 83 ms 167868 KB Output is correct
17 Correct 91 ms 167292 KB Output is correct
18 Correct 84 ms 165148 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 371 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 544 ms 217772 KB Output is correct
2 Correct 410 ms 217704 KB Output is correct
3 Correct 223 ms 175596 KB Output is correct
4 Correct 256 ms 175576 KB Output is correct
5 Correct 225 ms 175584 KB Output is correct
6 Correct 175 ms 175552 KB Output is correct
7 Correct 196 ms 175644 KB Output is correct
8 Correct 207 ms 174864 KB Output is correct
9 Correct 117 ms 165244 KB Output is correct
10 Correct 187 ms 174824 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 164680 KB Output is correct
2 Correct 87 ms 164580 KB Output is correct
3 Correct 87 ms 164684 KB Output is correct
4 Correct 79 ms 164588 KB Output is correct
5 Correct 82 ms 164676 KB Output is correct
6 Correct 91 ms 164900 KB Output is correct
7 Correct 98 ms 164868 KB Output is correct
8 Correct 74 ms 164804 KB Output is correct
9 Correct 74 ms 164716 KB Output is correct
10 Correct 76 ms 164676 KB Output is correct
11 Correct 79 ms 165508 KB Output is correct
12 Correct 92 ms 167784 KB Output is correct
13 Correct 91 ms 167836 KB Output is correct
14 Correct 84 ms 167944 KB Output is correct
15 Correct 81 ms 167948 KB Output is correct
16 Correct 83 ms 167868 KB Output is correct
17 Correct 91 ms 167292 KB Output is correct
18 Correct 84 ms 165148 KB Output is correct
19 Runtime error 302 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 85 ms 164680 KB Output is correct
2 Correct 87 ms 164580 KB Output is correct
3 Correct 87 ms 164684 KB Output is correct
4 Correct 79 ms 164588 KB Output is correct
5 Correct 82 ms 164676 KB Output is correct
6 Correct 91 ms 164900 KB Output is correct
7 Correct 98 ms 164868 KB Output is correct
8 Correct 74 ms 164804 KB Output is correct
9 Correct 74 ms 164716 KB Output is correct
10 Correct 76 ms 164676 KB Output is correct
11 Correct 79 ms 165508 KB Output is correct
12 Correct 92 ms 167784 KB Output is correct
13 Correct 91 ms 167836 KB Output is correct
14 Correct 84 ms 167944 KB Output is correct
15 Correct 81 ms 167948 KB Output is correct
16 Correct 83 ms 167868 KB Output is correct
17 Correct 91 ms 167292 KB Output is correct
18 Correct 84 ms 165148 KB Output is correct
19 Runtime error 371 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -