oj.uz

Submission #497578

# Submission time Handle Problem Language Result Execution time Memory
497578 2021-12-23T10:08:12 Z vinnipuh01 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 581 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 {
	vector <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.back();
			int mxx = -1;
			while ( l < v.size() && r < a.v.size() ) {
				if ( v[ l ] < a.v[ r ] ) {
					c.v.push_back( v[ l ] );
					l ++;
				}
				else {
					c.v.push_back( a.v[ r ] );
					if ( a.v[ r ] > mxx && a.v[ r ] < mx )
						mxx = a.v[ r ];
					r ++;
				}
			}
			while ( l < v.size() ) {
				c.v.push_back( v[ l ] );
				l ++;
			}
			while ( r < a.v.size() ) {
				c.v.push_back( a.v[ r ] );
				if ( a.v[ r ] > mxx && a.v[ r ] < mx )
					mxx = a.v[ r ];
				r ++;
			}
			if ( ~mxx )
				c.ans = max( c.ans, mx + mxx );
			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.push_back( 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.front() ) {
			auto it = lower_bound( t[ v ].v.begin(), t[ v ].v.end(), an.mx );
			it = --it;
			an.ans = max( an.ans, an.mx + *it );
		}
		an.mx = max( an.mx, t[ v ].v.back() );
		return;
	}
	int mid = ( tl + tr ) / 2;
	gett( v + v, tl, mid, l, r );
	gett( v + v + 1, mid + 1, tr, l, r );
}

struct Node2 {
	int mn, mx, inv;
	public :
		Node2 operator + ( Node2 a ) {
			Node2 c;
			c.inv = max( inv, a.inv );
			if ( a.mn < mx )
				c.inv = 1;
			c.mn = min( mn, a.mn );
			c.mx = max( mx, a.mx );
			return c;
		}
} t1[ 4000001 ];
 
void build1( int v, int tl, int tr ) {
	if ( tl == tr ) {
		t1[ v ].mn = a[ tl ];
		t1[ v ].mx = a[ tl ];
		t1[ v ].inv = 0;
		return;
	}
	int mid = ( tl + tr ) / 2;
	build1( v + v, tl, mid );
	build1( v + v + 1, mid + 1, tr );
	t1[ v ] = t1[ v + v ] + t1[ v + v + 1 ];
}
 
void gett1( int v, int tl, int tr, int l, int r ) {
	if ( tl > r || tr < l )
		return;
	if ( tl >= l && tr <= r ) {
		if ( t1[ v ].mn < mx || t1[ v ].inv )
			num = 1;
		mx = max( mx, t1[ v ].mx + 0ll );
		return;
	}
	int mid = ( tl + tr ) / 2;
	gett1( v + v, tl, mid, l, r );
	gett1( 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;
//	if ( n <= 2e5 && m <= 2e5 )
		build( 1, 1, n );
//	else
//		build1( 1, 1, n );
	while ( m -- ) {
		cin >> l >> r >> x;
//		if ( n <= 2e5 && m <= 2e5 ) {
			num = 0;
			an.mx = 0;
			an.ans = 0;
			gett( 1, 1, n, l, r );
			cout << ( x >= an.ans ) << "\n";
//		}
//		else {
//			num = 0;
//			mx = -1;
//			gett1( 1, 1, n, l, r );
//			cout << !num << "\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:54:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    while ( l < v.size() && r < a.v.size() ) {
      |            ~~^~~~~~~~~~
sortbooks.cpp:54:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    while ( l < v.size() && r < a.v.size() ) {
      |                            ~~^~~~~~~~~~~~
sortbooks.cpp:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    while ( l < v.size() ) {
      |            ~~^~~~~~~~~~
sortbooks.cpp:70:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    while ( r < a.v.size() ) {
      |            ~~^~~~~~~~~~~~
sortbooks.cpp: At global scope:
sortbooks.cpp:159:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  159 | main () {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125508 KB Output is correct
2 Correct 60 ms 125520 KB Output is correct
3 Correct 63 ms 125512 KB Output is correct
4 Correct 60 ms 125460 KB Output is correct
5 Correct 73 ms 125516 KB Output is correct
6 Correct 63 ms 125500 KB Output is correct
7 Correct 59 ms 125748 KB Output is correct
8 Correct 62 ms 125612 KB Output is correct
9 Correct 68 ms 125472 KB Output is correct
10 Correct 64 ms 125508 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125508 KB Output is correct
2 Correct 60 ms 125520 KB Output is correct
3 Correct 63 ms 125512 KB Output is correct
4 Correct 60 ms 125460 KB Output is correct
5 Correct 73 ms 125516 KB Output is correct
6 Correct 63 ms 125500 KB Output is correct
7 Correct 59 ms 125748 KB Output is correct
8 Correct 62 ms 125612 KB Output is correct
9 Correct 68 ms 125472 KB Output is correct
10 Correct 64 ms 125508 KB Output is correct
11 Correct 61 ms 125756 KB Output is correct
12 Correct 66 ms 126232 KB Output is correct
13 Correct 62 ms 126268 KB Output is correct
14 Correct 66 ms 126288 KB Output is correct
15 Correct 68 ms 126232 KB Output is correct
16 Correct 76 ms 126248 KB Output is correct
17 Correct 70 ms 126044 KB Output is correct
18 Correct 67 ms 126228 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 581 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 247 ms 139396 KB Output is correct
2 Correct 247 ms 139444 KB Output is correct
3 Correct 229 ms 139880 KB Output is correct
4 Correct 211 ms 139824 KB Output is correct
5 Correct 212 ms 139808 KB Output is correct
6 Correct 178 ms 140008 KB Output is correct
7 Correct 158 ms 139792 KB Output is correct
8 Correct 191 ms 139876 KB Output is correct
9 Correct 108 ms 126236 KB Output is correct
10 Correct 183 ms 139832 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125508 KB Output is correct
2 Correct 60 ms 125520 KB Output is correct
3 Correct 63 ms 125512 KB Output is correct
4 Correct 60 ms 125460 KB Output is correct
5 Correct 73 ms 125516 KB Output is correct
6 Correct 63 ms 125500 KB Output is correct
7 Correct 59 ms 125748 KB Output is correct
8 Correct 62 ms 125612 KB Output is correct
9 Correct 68 ms 125472 KB Output is correct
10 Correct 64 ms 125508 KB Output is correct
11 Correct 61 ms 125756 KB Output is correct
12 Correct 66 ms 126232 KB Output is correct
13 Correct 62 ms 126268 KB Output is correct
14 Correct 66 ms 126288 KB Output is correct
15 Correct 68 ms 126232 KB Output is correct
16 Correct 76 ms 126248 KB Output is correct
17 Correct 70 ms 126044 KB Output is correct
18 Correct 67 ms 126228 KB Output is correct
19 Correct 504 ms 154620 KB Output is correct
20 Correct 515 ms 154548 KB Output is correct
21 Correct 482 ms 155064 KB Output is correct
22 Correct 460 ms 155156 KB Output is correct
23 Correct 451 ms 154992 KB Output is correct
24 Correct 292 ms 154920 KB Output is correct
25 Correct 298 ms 154876 KB Output is correct
26 Correct 352 ms 154884 KB Output is correct
27 Correct 349 ms 155096 KB Output is correct
28 Correct 375 ms 154928 KB Output is correct
29 Correct 365 ms 155184 KB Output is correct
30 Correct 361 ms 154992 KB Output is correct
31 Correct 389 ms 155036 KB Output is correct
32 Correct 386 ms 155156 KB Output is correct
33 Correct 391 ms 154872 KB Output is correct
34 Correct 303 ms 155132 KB Output is correct
35 Correct 331 ms 154940 KB Output is correct
36 Correct 306 ms 155100 KB Output is correct
37 Correct 283 ms 154940 KB Output is correct
38 Correct 296 ms 154900 KB Output is correct
39 Correct 366 ms 154996 KB Output is correct
40 Correct 260 ms 142604 KB Output is correct
41 Correct 402 ms 154984 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 125508 KB Output is correct
2 Correct 60 ms 125520 KB Output is correct
3 Correct 63 ms 125512 KB Output is correct
4 Correct 60 ms 125460 KB Output is correct
5 Correct 73 ms 125516 KB Output is correct
6 Correct 63 ms 125500 KB Output is correct
7 Correct 59 ms 125748 KB Output is correct
8 Correct 62 ms 125612 KB Output is correct
9 Correct 68 ms 125472 KB Output is correct
10 Correct 64 ms 125508 KB Output is correct
11 Correct 61 ms 125756 KB Output is correct
12 Correct 66 ms 126232 KB Output is correct
13 Correct 62 ms 126268 KB Output is correct
14 Correct 66 ms 126288 KB Output is correct
15 Correct 68 ms 126232 KB Output is correct
16 Correct 76 ms 126248 KB Output is correct
17 Correct 70 ms 126044 KB Output is correct
18 Correct 67 ms 126228 KB Output is correct
19 Runtime error 581 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -