oj.uz

Submission #497503

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

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 58 ms 109892 KB Output is correct
2 Correct 53 ms 109888 KB Output is correct
3 Correct 56 ms 109940 KB Output is correct
4 Correct 53 ms 109900 KB Output is correct
5 Correct 66 ms 109932 KB Output is correct
6 Correct 54 ms 110100 KB Output is correct
7 Correct 55 ms 110136 KB Output is correct
8 Correct 63 ms 110060 KB Output is correct
9 Correct 60 ms 110020 KB Output is correct
10 Correct 55 ms 109892 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 109892 KB Output is correct
2 Correct 53 ms 109888 KB Output is correct
3 Correct 56 ms 109940 KB Output is correct
4 Correct 53 ms 109900 KB Output is correct
5 Correct 66 ms 109932 KB Output is correct
6 Correct 54 ms 110100 KB Output is correct
7 Correct 55 ms 110136 KB Output is correct
8 Correct 63 ms 110060 KB Output is correct
9 Correct 60 ms 110020 KB Output is correct
10 Correct 55 ms 109892 KB Output is correct
11 Correct 62 ms 110604 KB Output is correct
12 Correct 66 ms 113048 KB Output is correct
13 Correct 67 ms 113068 KB Output is correct
14 Correct 66 ms 113088 KB Output is correct
15 Correct 77 ms 113184 KB Output is correct
16 Correct 62 ms 113084 KB Output is correct
17 Correct 60 ms 112452 KB Output is correct
18 Correct 57 ms 110336 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 418 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 454 ms 162908 KB Output is correct
2 Correct 440 ms 162864 KB Output is correct
3 Correct 186 ms 120528 KB Output is correct
4 Correct 242 ms 120564 KB Output is correct
5 Correct 212 ms 120652 KB Output is correct
6 Correct 170 ms 120560 KB Output is correct
7 Correct 139 ms 120556 KB Output is correct
8 Correct 166 ms 119956 KB Output is correct
9 Correct 107 ms 110304 KB Output is correct
10 Correct 186 ms 119788 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 109892 KB Output is correct
2 Correct 53 ms 109888 KB Output is correct
3 Correct 56 ms 109940 KB Output is correct
4 Correct 53 ms 109900 KB Output is correct
5 Correct 66 ms 109932 KB Output is correct
6 Correct 54 ms 110100 KB Output is correct
7 Correct 55 ms 110136 KB Output is correct
8 Correct 63 ms 110060 KB Output is correct
9 Correct 60 ms 110020 KB Output is correct
10 Correct 55 ms 109892 KB Output is correct
11 Correct 62 ms 110604 KB Output is correct
12 Correct 66 ms 113048 KB Output is correct
13 Correct 67 ms 113068 KB Output is correct
14 Correct 66 ms 113088 KB Output is correct
15 Correct 77 ms 113184 KB Output is correct
16 Correct 62 ms 113084 KB Output is correct
17 Correct 60 ms 112452 KB Output is correct
18 Correct 57 ms 110336 KB Output is correct
19 Runtime error 430 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 58 ms 109892 KB Output is correct
2 Correct 53 ms 109888 KB Output is correct
3 Correct 56 ms 109940 KB Output is correct
4 Correct 53 ms 109900 KB Output is correct
5 Correct 66 ms 109932 KB Output is correct
6 Correct 54 ms 110100 KB Output is correct
7 Correct 55 ms 110136 KB Output is correct
8 Correct 63 ms 110060 KB Output is correct
9 Correct 60 ms 110020 KB Output is correct
10 Correct 55 ms 109892 KB Output is correct
11 Correct 62 ms 110604 KB Output is correct
12 Correct 66 ms 113048 KB Output is correct
13 Correct 67 ms 113068 KB Output is correct
14 Correct 66 ms 113088 KB Output is correct
15 Correct 77 ms 113184 KB Output is correct
16 Correct 62 ms 113084 KB Output is correct
17 Correct 60 ms 112452 KB Output is correct
18 Correct 57 ms 110336 KB Output is correct
19 Runtime error 418 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -