oj.uz

Submission #497520

# Submission time Handle Problem Language Result Execution time Memory
497520 2021-12-23T08:11:40 Z vinnipuh01 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
38 / 100
 1986 ms 240292 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();
			if ( a.v.front() < mx ) {
				auto it = lower_bound( a.v.begin(), a.v.end(), mx );
				it = --it;
				c.ans = max( c.ans, *it + mx );
			}
			while ( l < v.size() && v[ l ] < ( c.ans + 1 ) / 2 )
				l ++;
			while ( r < a.v.size() && a.v[ r ] < ( c.ans + 1 ) / 2 )
				r ++;
			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 ] );
					r ++;
				}
			}
			while ( l < v.size() ) {
				c.v.push_back( v[ l ] );
				l ++;
			}
			while ( r < a.v.size() ) {
				c.v.push_back( a.v[ r ] );
				r ++;
			}
			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.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 );
}
 
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:58:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    while ( l < v.size() && v[ l ] < ( c.ans + 1 ) / 2 )
      |            ~~^~~~~~~~~~
sortbooks.cpp:60:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    while ( r < a.v.size() && a.v[ r ] < ( c.ans + 1 ) / 2 )
      |            ~~^~~~~~~~~~~~
sortbooks.cpp:62:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    while ( l < v.size() && r < a.v.size() ) {
      |            ~~^~~~~~~~~~
sortbooks.cpp:62:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    while ( l < v.size() && r < a.v.size() ) {
      |                            ~~^~~~~~~~~~~~
sortbooks.cpp:72:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    while ( l < v.size() ) {
      |            ~~^~~~~~~~~~
sortbooks.cpp:76:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    while ( r < a.v.size() ) {
      |            ~~^~~~~~~~~~~~
sortbooks.cpp: At global scope:
sortbooks.cpp:120:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  120 | main () {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94156 KB Output is correct
2 Correct 59 ms 94228 KB Output is correct
3 Correct 48 ms 94160 KB Output is correct
4 Correct 51 ms 94192 KB Output is correct
5 Correct 48 ms 94148 KB Output is correct
6 Correct 52 ms 94276 KB Output is correct
7 Correct 56 ms 94264 KB Output is correct
8 Correct 55 ms 94276 KB Output is correct
9 Correct 53 ms 94256 KB Output is correct
10 Correct 49 ms 94152 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94156 KB Output is correct
2 Correct 59 ms 94228 KB Output is correct
3 Correct 48 ms 94160 KB Output is correct
4 Correct 51 ms 94192 KB Output is correct
5 Correct 48 ms 94148 KB Output is correct
6 Correct 52 ms 94276 KB Output is correct
7 Correct 56 ms 94264 KB Output is correct
8 Correct 55 ms 94276 KB Output is correct
9 Correct 53 ms 94256 KB Output is correct
10 Correct 49 ms 94152 KB Output is correct
11 Incorrect 50 ms 94276 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1774 ms 162672 KB Output is correct
2 Correct 1855 ms 163040 KB Output is correct
3 Correct 1841 ms 163092 KB Output is correct
4 Correct 1805 ms 163236 KB Output is correct
5 Correct 1986 ms 240292 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 101060 KB Output is correct
2 Correct 151 ms 101064 KB Output is correct
3 Correct 184 ms 108316 KB Output is correct
4 Correct 181 ms 108396 KB Output is correct
5 Correct 183 ms 108380 KB Output is correct
6 Correct 161 ms 108072 KB Output is correct
7 Correct 200 ms 108116 KB Output is correct
8 Correct 172 ms 107156 KB Output is correct
9 Correct 82 ms 94700 KB Output is correct
10 Correct 182 ms 107212 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94156 KB Output is correct
2 Correct 59 ms 94228 KB Output is correct
3 Correct 48 ms 94160 KB Output is correct
4 Correct 51 ms 94192 KB Output is correct
5 Correct 48 ms 94148 KB Output is correct
6 Correct 52 ms 94276 KB Output is correct
7 Correct 56 ms 94264 KB Output is correct
8 Correct 55 ms 94276 KB Output is correct
9 Correct 53 ms 94256 KB Output is correct
10 Correct 49 ms 94152 KB Output is correct
11 Incorrect 50 ms 94276 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94156 KB Output is correct
2 Correct 59 ms 94228 KB Output is correct
3 Correct 48 ms 94160 KB Output is correct
4 Correct 51 ms 94192 KB Output is correct
5 Correct 48 ms 94148 KB Output is correct
6 Correct 52 ms 94276 KB Output is correct
7 Correct 56 ms 94264 KB Output is correct
8 Correct 55 ms 94276 KB Output is correct
9 Correct 53 ms 94256 KB Output is correct
10 Correct 49 ms 94152 KB Output is correct
11 Incorrect 50 ms 94276 KB Output isn't correct
12 Halted 0 ms 0 KB -