oj.uz

Submission #896025

# Submission time Handle Problem Language Result Execution time Memory
896025 2023-12-31T13:04:06 Z thunopro Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1068 ms 101764 KB 
#include<bits/stdc++.h>
using namespace std ; 
#define ll long long 
#define maxn 1000009 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1 
#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1  

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 
const int LOG = 18 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<ll> vl ; 
typedef vector<pii> vii ; 
 
void add ( int &a , int b ) 
{
	a += b ;
	if ( a < 0 ) a += mod ; 
	if ( a >= mod ) a -= mod ; 
}

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

int n , nq ; 
int a [maxn] ; 
int le [maxn] ; 
int ans [maxn] ; 
struct even
{
	int l , k , id ; 
}; 
vector <even> event [maxn] ; 

int T [maxn*4] ; 
void update ( int id , int l , int r , int pos , int w ) 
{
	if ( l > pos || r < pos ) return ; 
	if ( l == r ) 
	{
		T [id] = w ; 
		return ; 
	}
	int mid = (l+r)/2 ; 
	update (left,l,mid,pos,w) ; update (right,mid+1,r,pos,w) ; 
	T [id] = max (T[left],T[right]) ; 
}
int get ( int id , int l , int r , int u , int v ) 
{
	if ( l > v || r < u ) return 0 ; 
	if ( u <= l && r <= v ) return T [id] ; 
	int mid = (l+r)/2 ; 
	return max (get(left,l,mid,u,v),get(right,mid+1,r,u,v)) ; 	
}
int main () 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0) ; 
//	rf () ; 
	cin >> n >> nq ; 
	
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		cin >> a [i] ; 
	}
	
	for ( int i = 1 ; i <= nq ; i ++ ) 
	{
		int l , r , k ; cin >> l >> r >> k ; 
		event [r] . pb ({l,k,i}) ; 
	}
	
	stack <int> stk ; 
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		while (!stk.empty()&&a[stk.top()]<=a[i]) stk.pop() ; 
		le [i] = stk.empty() ? 0 : stk.top() ; 
		stk.push (i) ; 
	}
	
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		if ( le [i] ) update (1,1,n,le[i],a[le[i]]+a[i]) ;
		for ( auto x : event [i] ) 
		{
			int Max = get (1,1,n,x.l,i) ; 
			ans [x.id] = ( Max <= x.k ) ; 
		}
	}
	
	for ( int i = 1 ; i <= nq ; i ++ ) cout << ans [i] << "\n" ; 
}

// range , error , check special , ... 
// find key , find key 
//'-std=c++11' stay hard 
// there is no tomorrow

Compilation message

sortbooks.cpp: In function 'void rf()':
sortbooks.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29276 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Correct 6 ms 29144 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 7 ms 29020 KB Output is correct
10 Correct 6 ms 29020 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29276 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Correct 6 ms 29144 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 7 ms 29020 KB Output is correct
10 Correct 6 ms 29020 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 8 ms 29276 KB Output is correct
14 Correct 9 ms 29532 KB Output is correct
15 Correct 9 ms 29532 KB Output is correct
16 Correct 9 ms 29276 KB Output is correct
17 Correct 8 ms 29272 KB Output is correct
18 Correct 8 ms 29276 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1058 ms 92528 KB Output is correct
2 Correct 1061 ms 101728 KB Output is correct
3 Correct 1063 ms 101508 KB Output is correct
4 Correct 1068 ms 101696 KB Output is correct
5 Correct 910 ms 93176 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 39584 KB Output is correct
2 Correct 75 ms 39396 KB Output is correct
3 Correct 63 ms 37460 KB Output is correct
4 Correct 66 ms 37456 KB Output is correct
5 Correct 66 ms 37384 KB Output is correct
6 Correct 54 ms 39248 KB Output is correct
7 Correct 57 ms 38896 KB Output is correct
8 Correct 63 ms 37128 KB Output is correct
9 Correct 33 ms 34060 KB Output is correct
10 Correct 63 ms 37056 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29276 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Correct 6 ms 29144 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 7 ms 29020 KB Output is correct
10 Correct 6 ms 29020 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 8 ms 29276 KB Output is correct
14 Correct 9 ms 29532 KB Output is correct
15 Correct 9 ms 29532 KB Output is correct
16 Correct 9 ms 29276 KB Output is correct
17 Correct 8 ms 29272 KB Output is correct
18 Correct 8 ms 29276 KB Output is correct
19 Correct 183 ms 48792 KB Output is correct
20 Correct 173 ms 48628 KB Output is correct
21 Correct 155 ms 47908 KB Output is correct
22 Correct 156 ms 47968 KB Output is correct
23 Correct 154 ms 47980 KB Output is correct
24 Correct 123 ms 45648 KB Output is correct
25 Correct 127 ms 45892 KB Output is correct
26 Correct 137 ms 45960 KB Output is correct
27 Correct 133 ms 45908 KB Output is correct
28 Correct 138 ms 46160 KB Output is correct
29 Correct 147 ms 46348 KB Output is correct
30 Correct 151 ms 46420 KB Output is correct
31 Correct 145 ms 46420 KB Output is correct
32 Correct 151 ms 46536 KB Output is correct
33 Correct 153 ms 46548 KB Output is correct
34 Correct 113 ms 47184 KB Output is correct
35 Correct 112 ms 47184 KB Output is correct
36 Correct 119 ms 47188 KB Output is correct
37 Correct 122 ms 46932 KB Output is correct
38 Correct 123 ms 47184 KB Output is correct
39 Correct 142 ms 45836 KB Output is correct
40 Correct 100 ms 43700 KB Output is correct
41 Correct 126 ms 44440 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29276 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Correct 6 ms 29144 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 7 ms 29020 KB Output is correct
10 Correct 6 ms 29020 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 8 ms 29276 KB Output is correct
14 Correct 9 ms 29532 KB Output is correct
15 Correct 9 ms 29532 KB Output is correct
16 Correct 9 ms 29276 KB Output is correct
17 Correct 8 ms 29272 KB Output is correct
18 Correct 8 ms 29276 KB Output is correct
19 Correct 1058 ms 92528 KB Output is correct
20 Correct 1061 ms 101728 KB Output is correct
21 Correct 1063 ms 101508 KB Output is correct
22 Correct 1068 ms 101696 KB Output is correct
23 Correct 910 ms 93176 KB Output is correct
24 Correct 90 ms 39584 KB Output is correct
25 Correct 75 ms 39396 KB Output is correct
26 Correct 63 ms 37460 KB Output is correct
27 Correct 66 ms 37456 KB Output is correct
28 Correct 66 ms 37384 KB Output is correct
29 Correct 54 ms 39248 KB Output is correct
30 Correct 57 ms 38896 KB Output is correct
31 Correct 63 ms 37128 KB Output is correct
32 Correct 33 ms 34060 KB Output is correct
33 Correct 63 ms 37056 KB Output is correct
34 Correct 183 ms 48792 KB Output is correct
35 Correct 173 ms 48628 KB Output is correct
36 Correct 155 ms 47908 KB Output is correct
37 Correct 156 ms 47968 KB Output is correct
38 Correct 154 ms 47980 KB Output is correct
39 Correct 123 ms 45648 KB Output is correct
40 Correct 127 ms 45892 KB Output is correct
41 Correct 137 ms 45960 KB Output is correct
42 Correct 133 ms 45908 KB Output is correct
43 Correct 138 ms 46160 KB Output is correct
44 Correct 147 ms 46348 KB Output is correct
45 Correct 151 ms 46420 KB Output is correct
46 Correct 145 ms 46420 KB Output is correct
47 Correct 151 ms 46536 KB Output is correct
48 Correct 153 ms 46548 KB Output is correct
49 Correct 113 ms 47184 KB Output is correct
50 Correct 112 ms 47184 KB Output is correct
51 Correct 119 ms 47188 KB Output is correct
52 Correct 122 ms 46932 KB Output is correct
53 Correct 123 ms 47184 KB Output is correct
54 Correct 142 ms 45836 KB Output is correct
55 Correct 100 ms 43700 KB Output is correct
56 Correct 126 ms 44440 KB Output is correct
57 Correct 1060 ms 101764 KB Output is correct
58 Correct 1051 ms 101756 KB Output is correct
59 Correct 974 ms 100384 KB Output is correct
60 Correct 995 ms 100444 KB Output is correct
61 Correct 992 ms 100280 KB Output is correct
62 Correct 989 ms 100120 KB Output is correct
63 Correct 627 ms 88548 KB Output is correct
64 Correct 642 ms 89004 KB Output is correct
65 Correct 861 ms 91624 KB Output is correct
66 Correct 890 ms 91628 KB Output is correct
67 Correct 875 ms 91752 KB Output is correct
68 Correct 873 ms 93524 KB Output is correct
69 Correct 901 ms 93472 KB Output is correct
70 Correct 903 ms 93156 KB Output is correct
71 Correct 874 ms 93460 KB Output is correct
72 Correct 884 ms 93012 KB Output is correct
73 Correct 605 ms 88492 KB Output is correct
74 Correct 566 ms 89840 KB Output is correct
75 Correct 598 ms 88552 KB Output is correct
76 Correct 549 ms 88824 KB Output is correct
77 Correct 564 ms 88524 KB Output is correct
78 Correct 772 ms 89860 KB Output is correct
79 Correct 552 ms 77048 KB Output is correct
80 Correct 791 ms 82820 KB Output is correct