oj.uz

답안 #497413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 851 ms 22836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -