oj.uz

Submission #497576

# Submission time Handle Problem Language Result Execution time Memory
497576 2021-12-23T10:06:48 Z vinnipuh01 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
77 / 100
 1083 ms 156144 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 68 ms 125476 KB Output is correct
2 Correct 70 ms 125504 KB Output is correct
3 Correct 59 ms 125532 KB Output is correct
4 Correct 57 ms 125528 KB Output is correct
5 Correct 58 ms 125496 KB Output is correct
6 Correct 58 ms 125516 KB Output is correct
7 Correct 74 ms 125572 KB Output is correct
8 Correct 63 ms 125508 KB Output is correct
9 Correct 58 ms 125508 KB Output is correct
10 Correct 56 ms 125508 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 125476 KB Output is correct
2 Correct 70 ms 125504 KB Output is correct
3 Correct 59 ms 125532 KB Output is correct
4 Correct 57 ms 125528 KB Output is correct
5 Correct 58 ms 125496 KB Output is correct
6 Correct 58 ms 125516 KB Output is correct
7 Correct 74 ms 125572 KB Output is correct
8 Correct 63 ms 125508 KB Output is correct
9 Correct 58 ms 125508 KB Output is correct
10 Correct 56 ms 125508 KB Output is correct
11 Correct 59 ms 125624 KB Output is correct
12 Correct 62 ms 126232 KB Output is correct
13 Correct 70 ms 126276 KB Output is correct
14 Correct 68 ms 126152 KB Output is correct
15 Correct 61 ms 126268 KB Output is correct
16 Correct 63 ms 126248 KB Output is correct
17 Correct 66 ms 125904 KB Output is correct
18 Correct 66 ms 126160 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 156136 KB Output is correct
2 Correct 1010 ms 155988 KB Output is correct
3 Correct 1022 ms 155988 KB Output is correct
4 Correct 979 ms 156104 KB Output is correct
5 Correct 982 ms 155976 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 139428 KB Output is correct
2 Correct 214 ms 139412 KB Output is correct
3 Correct 202 ms 139500 KB Output is correct
4 Correct 192 ms 139504 KB Output is correct
5 Correct 229 ms 139528 KB Output is correct
6 Correct 156 ms 139516 KB Output is correct
7 Correct 154 ms 139496 KB Output is correct
8 Correct 173 ms 139516 KB Output is correct
9 Correct 95 ms 125884 KB Output is correct
10 Correct 213 ms 139528 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 125476 KB Output is correct
2 Correct 70 ms 125504 KB Output is correct
3 Correct 59 ms 125532 KB Output is correct
4 Correct 57 ms 125528 KB Output is correct
5 Correct 58 ms 125496 KB Output is correct
6 Correct 58 ms 125516 KB Output is correct
7 Correct 74 ms 125572 KB Output is correct
8 Correct 63 ms 125508 KB Output is correct
9 Correct 58 ms 125508 KB Output is correct
10 Correct 56 ms 125508 KB Output is correct
11 Correct 59 ms 125624 KB Output is correct
12 Correct 62 ms 126232 KB Output is correct
13 Correct 70 ms 126276 KB Output is correct
14 Correct 68 ms 126152 KB Output is correct
15 Correct 61 ms 126268 KB Output is correct
16 Correct 63 ms 126248 KB Output is correct
17 Correct 66 ms 125904 KB Output is correct
18 Correct 66 ms 126160 KB Output is correct
19 Correct 500 ms 154480 KB Output is correct
20 Correct 497 ms 154440 KB Output is correct
21 Correct 411 ms 154604 KB Output is correct
22 Correct 423 ms 154596 KB Output is correct
23 Correct 408 ms 154584 KB Output is correct
24 Correct 292 ms 154672 KB Output is correct
25 Correct 274 ms 154580 KB Output is correct
26 Correct 350 ms 154632 KB Output is correct
27 Correct 340 ms 154544 KB Output is correct
28 Correct 349 ms 154480 KB Output is correct
29 Correct 396 ms 154492 KB Output is correct
30 Correct 374 ms 154604 KB Output is correct
31 Correct 359 ms 154544 KB Output is correct
32 Correct 355 ms 154668 KB Output is correct
33 Correct 360 ms 154544 KB Output is correct
34 Correct 277 ms 154580 KB Output is correct
35 Correct 276 ms 154544 KB Output is correct
36 Correct 277 ms 154712 KB Output is correct
37 Correct 271 ms 154576 KB Output is correct
38 Correct 275 ms 154608 KB Output is correct
39 Correct 334 ms 154508 KB Output is correct
40 Correct 238 ms 142212 KB Output is correct
41 Correct 356 ms 154544 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 125476 KB Output is correct
2 Correct 70 ms 125504 KB Output is correct
3 Correct 59 ms 125532 KB Output is correct
4 Correct 57 ms 125528 KB Output is correct
5 Correct 58 ms 125496 KB Output is correct
6 Correct 58 ms 125516 KB Output is correct
7 Correct 74 ms 125572 KB Output is correct
8 Correct 63 ms 125508 KB Output is correct
9 Correct 58 ms 125508 KB Output is correct
10 Correct 56 ms 125508 KB Output is correct
11 Correct 59 ms 125624 KB Output is correct
12 Correct 62 ms 126232 KB Output is correct
13 Correct 70 ms 126276 KB Output is correct
14 Correct 68 ms 126152 KB Output is correct
15 Correct 61 ms 126268 KB Output is correct
16 Correct 63 ms 126248 KB Output is correct
17 Correct 66 ms 125904 KB Output is correct
18 Correct 66 ms 126160 KB Output is correct
19 Correct 1083 ms 156136 KB Output is correct
20 Correct 1010 ms 155988 KB Output is correct
21 Correct 1022 ms 155988 KB Output is correct
22 Correct 979 ms 156104 KB Output is correct
23 Correct 982 ms 155976 KB Output is correct
24 Correct 237 ms 139428 KB Output is correct
25 Correct 214 ms 139412 KB Output is correct
26 Correct 202 ms 139500 KB Output is correct
27 Correct 192 ms 139504 KB Output is correct
28 Correct 229 ms 139528 KB Output is correct
29 Correct 156 ms 139516 KB Output is correct
30 Correct 154 ms 139496 KB Output is correct
31 Correct 173 ms 139516 KB Output is correct
32 Correct 95 ms 125884 KB Output is correct
33 Correct 213 ms 139528 KB Output is correct
34 Correct 500 ms 154480 KB Output is correct
35 Correct 497 ms 154440 KB Output is correct
36 Correct 411 ms 154604 KB Output is correct
37 Correct 423 ms 154596 KB Output is correct
38 Correct 408 ms 154584 KB Output is correct
39 Correct 292 ms 154672 KB Output is correct
40 Correct 274 ms 154580 KB Output is correct
41 Correct 350 ms 154632 KB Output is correct
42 Correct 340 ms 154544 KB Output is correct
43 Correct 349 ms 154480 KB Output is correct
44 Correct 396 ms 154492 KB Output is correct
45 Correct 374 ms 154604 KB Output is correct
46 Correct 359 ms 154544 KB Output is correct
47 Correct 355 ms 154668 KB Output is correct
48 Correct 360 ms 154544 KB Output is correct
49 Correct 277 ms 154580 KB Output is correct
50 Correct 276 ms 154544 KB Output is correct
51 Correct 277 ms 154712 KB Output is correct
52 Correct 271 ms 154576 KB Output is correct
53 Correct 275 ms 154608 KB Output is correct
54 Correct 334 ms 154508 KB Output is correct
55 Correct 238 ms 142212 KB Output is correct
56 Correct 356 ms 154544 KB Output is correct
57 Incorrect 955 ms 156144 KB Output isn't correct
58 Halted 0 ms 0 KB -