oj.uz

Submission #497523

# Submission time Handle Problem Language Result Execution time Memory
497523 2021-12-23T08:12:28 Z vinnipuh01 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
25 / 100
 2094 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();
			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[ 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 );
}
 
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 74 ms 125508 KB Output is correct
2 Correct 70 ms 125472 KB Output is correct
3 Correct 76 ms 125476 KB Output is correct
4 Correct 67 ms 125512 KB Output is correct
5 Correct 69 ms 125572 KB Output is correct
6 Correct 67 ms 125504 KB Output is correct
7 Correct 74 ms 125576 KB Output is correct
8 Correct 81 ms 125584 KB Output is correct
9 Correct 72 ms 125532 KB Output is correct
10 Correct 67 ms 125504 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 125508 KB Output is correct
2 Correct 70 ms 125472 KB Output is correct
3 Correct 76 ms 125476 KB Output is correct
4 Correct 67 ms 125512 KB Output is correct
5 Correct 69 ms 125572 KB Output is correct
6 Correct 67 ms 125504 KB Output is correct
7 Correct 74 ms 125576 KB Output is correct
8 Correct 81 ms 125584 KB Output is correct
9 Correct 72 ms 125532 KB Output is correct
10 Correct 67 ms 125504 KB Output is correct
11 Incorrect 75 ms 125632 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1976 ms 194056 KB Output is correct
2 Correct 1959 ms 194072 KB Output is correct
3 Correct 2094 ms 194032 KB Output is correct
4 Correct 2055 ms 194100 KB Output is correct
5 Runtime error 470 ms 262148 KB Execution killed with signal 9

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 132340 KB Output is correct
2 Correct 170 ms 132412 KB Output is correct
3 Correct 215 ms 139464 KB Output is correct
4 Correct 265 ms 139436 KB Output is correct
5 Correct 279 ms 139380 KB Output is correct
6 Correct 169 ms 139168 KB Output is correct
7 Correct 221 ms 139208 KB Output is correct
8 Correct 230 ms 138296 KB Output is correct
9 Correct 114 ms 125692 KB Output is correct
10 Correct 186 ms 138376 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 125508 KB Output is correct
2 Correct 70 ms 125472 KB Output is correct
3 Correct 76 ms 125476 KB Output is correct
4 Correct 67 ms 125512 KB Output is correct
5 Correct 69 ms 125572 KB Output is correct
6 Correct 67 ms 125504 KB Output is correct
7 Correct 74 ms 125576 KB Output is correct
8 Correct 81 ms 125584 KB Output is correct
9 Correct 72 ms 125532 KB Output is correct
10 Correct 67 ms 125504 KB Output is correct
11 Incorrect 75 ms 125632 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 125508 KB Output is correct
2 Correct 70 ms 125472 KB Output is correct
3 Correct 76 ms 125476 KB Output is correct
4 Correct 67 ms 125512 KB Output is correct
5 Correct 69 ms 125572 KB Output is correct
6 Correct 67 ms 125504 KB Output is correct
7 Correct 74 ms 125576 KB Output is correct
8 Correct 81 ms 125584 KB Output is correct
9 Correct 72 ms 125532 KB Output is correct
10 Correct 67 ms 125504 KB Output is correct
11 Incorrect 75 ms 125632 KB Output isn't correct
12 Halted 0 ms 0 KB -