oj.uz

Submission #497413

# Submission time Handle Problem Language Result Execution time Memory
497413 2021-12-23T04:57:19 Z vinnipuh01 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 22836 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 int  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 {
	int mn, mx;
	public :
		Node operator + ( Node a ) {
			Node c;
			c.mn = min( mn, a.mn );
			c.mx = max( mx, a.mx );
			return c;
		}
} t[ 4000001 ];

int n, m, a[ 1000001 ];

void build( int v, int tl, int tr ) {
	if ( tl == tr ) {
		t[ v ].mn = a[ tl ];
		t[ v ].mx = a[ tl ];
		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 ) {
		if ( t[ v ].mn > mx )
			num = 1;
		mx = max( mx, t[ v ].mx + 0ll );
		return;
	}
	int mid = ( tl + tr ) / 2;
	gett( v + v, tl, mid, l, r );
	gett( v + v + 1, mid + 1, tr, l, r );
}

int 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 ];
		mn = min( mn, a[ i ] + 0ll );
	}
	int l, r, x;
	build( 1, 1, n );
	while ( m -- ) {
		cin >> l >> r >> x;
		if ( x < mn ) {
			num = 0;
			mx = 0;
			gett( 1, 1, n, l, r );
			cout << !num << "\n";
			continue;
		}
		mx = a[ l ];
		ans = 0;
		for ( int i = l + 1; i <= r; i ++ ) {
			if ( a[ i ] < mx )
				ans = max( ans, mx + a[ i ] );
			else
				mx = a[ i ];
		}
		cout << ( ans <= x ) << "\n";
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 6 ms 460 KB Output is correct
13 Correct 7 ms 460 KB Output is correct
14 Correct 12 ms 476 KB Output is correct
15 Correct 11 ms 476 KB Output is correct
16 Correct 15 ms 460 KB Output is correct
17 Correct 10 ms 332 KB Output is correct
18 Correct 15 ms 476 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 851 ms 22836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2515 ms 3292 KB Output is correct
2 Execution timed out 3072 ms 2888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 6 ms 460 KB Output is correct
13 Correct 7 ms 460 KB Output is correct
14 Correct 12 ms 476 KB Output is correct
15 Correct 11 ms 476 KB Output is correct
16 Correct 15 ms 460 KB Output is correct
17 Correct 10 ms 332 KB Output is correct
18 Correct 15 ms 476 KB Output is correct
19 Execution timed out 3082 ms 5308 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 6 ms 460 KB Output is correct
13 Correct 7 ms 460 KB Output is correct
14 Correct 12 ms 476 KB Output is correct
15 Correct 11 ms 476 KB Output is correct
16 Correct 15 ms 460 KB Output is correct
17 Correct 10 ms 332 KB Output is correct
18 Correct 15 ms 476 KB Output is correct
19 Incorrect 851 ms 22836 KB Output isn't correct
20 Halted 0 ms 0 KB -