oj.uz

Submission #343676

# Submission time Handle Problem Language Result Execution time Memory
343676 2021-01-04T11:22:44 Z Bill_00 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 2230 ms 262148 KB 
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 100000000000000000
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pp push
#define M 1000001
typedef long long ll;
using namespace std;

struct node{
	int ans;
	vector<int>vec;
};

node a[4*M];

int s[M];
void build(int id,int l,int r){
	if(l==r){
		a[id].ans=-1e9;
		a[id].vec.pb(s[l]);
		return;
	}
	int m=l+r>>1;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
	if(a[id*2].vec[a[id*2].vec.size()-1]<=a[id*2+1].vec[0]){
		a[id].ans=max(a[id*2].ans,a[id*2+1].ans);
	}
	else{
		int ii=(lower_bound(a[id*2+1].vec.begin(),a[id*2+1].vec.end(),a[id*2].vec[a[id*2].vec.size()-1])-a[id*2+1].vec.begin());
		a[id].ans=max(max(a[id*2].ans,a[id*2+1].ans),a[id*2].vec[a[id*2].vec.size()-1]+a[id*2+1].vec[ii-1]);
	}
	int i=0,j=0;
	while(i<a[id*2].vec.size() && j<a[id*2+1].vec.size()){
		if(a[id*2].vec[i]>a[id*2+1].vec[j]){
			a[id].vec.pb(a[id*2+1].vec[j]);
			j++;
		}
		else{
			a[id].vec.pb(a[id*2].vec[i]);
			i++;
		}
	}
	while(i<a[id*2].vec.size()){
		a[id].vec.pb(a[id*2].vec[i]);
		i++;
	}
	while(j<a[id*2+1].vec.size()){
		a[id].vec.pb(a[id*2+1].vec[j]);
		j++;
	}
}
int query1(int id,int l,int r,int L,int R){
	if(r<L || R<l){
		return -1e9;
	}
	if(L<=l && r<=R){
		return a[id].vec[a[id].vec.size()-1];
	}
	int m=l+r>>1;
	return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R));
}
int query2(int id,int l,int r,int L,int R,int k){
	if(r<L || R<l){
		return -1e9;
	}
	if(L<=l && r<=R){
		if(a[id].vec[0]>=k) return -1e9;
		else{
			int ii=(lower_bound(a[id].vec.begin(),a[id].vec.end(),k)-a[id].vec.begin());
			return a[id].vec[ii-1];
		}
	}
	int m=l+r>>1;
	return max(query2(id*2,l,m,L,R,k),query2(id*2+1,m+1,r,L,R,k));
}
int query(int id,int l,int r,int L,int R){
	// cout << id << '\n';
	if(r<L || R<l){
		return -1e9;
	}
	if(L<=l && r<=R){
		return a[id].ans;
	}
	int m=l+r>>1;
	int b=query1(id*2,l,m,L,R);
	int c=query2(id*2+1,m+1,r,L,R,b);
	// cout << id << ' ' << b << ' ' << c << '\n';
	return max(max(query(id*2,l,m,L,R),query(id*2+1,m+1,r,L,R)),b+c);
	
}
int main(){
	// ios_base::sync_with_stdio(NULL);
	// cin.tie(NULL);
	// cout.tie(NULL);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> s[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int l,r,k;
		cin >> l >> r >> k;
		if(k>=query(1,1,n,l,r)) cout << 1 << '\n';
		else cout << 0 << '\n';
	}
}

Compilation message

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:27:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int m=l+r>>1;
      |        ~^~
sortbooks.cpp:38:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  while(i<a[id*2].vec.size() && j<a[id*2+1].vec.size()){
      |        ~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:38:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  while(i<a[id*2].vec.size() && j<a[id*2+1].vec.size()){
      |                                ~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:48:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  while(i<a[id*2].vec.size()){
      |        ~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:52:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  while(j<a[id*2+1].vec.size()){
      |        ~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp: In function 'int query1(int, int, int, int, int)':
sortbooks.cpp:64:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int m=l+r>>1;
      |        ~^~
sortbooks.cpp: In function 'int query2(int, int, int, int, int, int)':
sortbooks.cpp:78:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |  int m=l+r>>1;
      |        ~^~
sortbooks.cpp: In function 'int query(int, int, int, int, int)':
sortbooks.cpp:89:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |  int m=l+r>>1;
      |        ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 125548 KB Output is correct
2 Correct 76 ms 125548 KB Output is correct
3 Correct 78 ms 125548 KB Output is correct
4 Correct 78 ms 125548 KB Output is correct
5 Correct 77 ms 125548 KB Output is correct
6 Correct 80 ms 125548 KB Output is correct
7 Correct 80 ms 125548 KB Output is correct
8 Correct 80 ms 125548 KB Output is correct
9 Correct 79 ms 125548 KB Output is correct
10 Correct 79 ms 125548 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 125548 KB Output is correct
2 Correct 76 ms 125548 KB Output is correct
3 Correct 78 ms 125548 KB Output is correct
4 Correct 78 ms 125548 KB Output is correct
5 Correct 77 ms 125548 KB Output is correct
6 Correct 80 ms 125548 KB Output is correct
7 Correct 80 ms 125548 KB Output is correct
8 Correct 80 ms 125548 KB Output is correct
9 Correct 79 ms 125548 KB Output is correct
10 Correct 79 ms 125548 KB Output is correct
11 Correct 92 ms 125676 KB Output is correct
12 Correct 95 ms 126188 KB Output is correct
13 Correct 98 ms 126188 KB Output is correct
14 Correct 108 ms 126232 KB Output is correct
15 Correct 111 ms 126316 KB Output is correct
16 Correct 103 ms 126188 KB Output is correct
17 Correct 100 ms 126152 KB Output is correct
18 Correct 102 ms 126188 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 884 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 997 ms 139368 KB Output is correct
2 Correct 979 ms 139384 KB Output is correct
3 Correct 917 ms 139548 KB Output is correct
4 Correct 904 ms 139536 KB Output is correct
5 Correct 893 ms 139492 KB Output is correct
6 Correct 805 ms 139620 KB Output is correct
7 Correct 816 ms 139492 KB Output is correct
8 Correct 774 ms 139428 KB Output is correct
9 Correct 432 ms 125804 KB Output is correct
10 Correct 773 ms 139496 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 125548 KB Output is correct
2 Correct 76 ms 125548 KB Output is correct
3 Correct 78 ms 125548 KB Output is correct
4 Correct 78 ms 125548 KB Output is correct
5 Correct 77 ms 125548 KB Output is correct
6 Correct 80 ms 125548 KB Output is correct
7 Correct 80 ms 125548 KB Output is correct
8 Correct 80 ms 125548 KB Output is correct
9 Correct 79 ms 125548 KB Output is correct
10 Correct 79 ms 125548 KB Output is correct
11 Correct 92 ms 125676 KB Output is correct
12 Correct 95 ms 126188 KB Output is correct
13 Correct 98 ms 126188 KB Output is correct
14 Correct 108 ms 126232 KB Output is correct
15 Correct 111 ms 126316 KB Output is correct
16 Correct 103 ms 126188 KB Output is correct
17 Correct 100 ms 126152 KB Output is correct
18 Correct 102 ms 126188 KB Output is correct
19 Correct 2208 ms 154088 KB Output is correct
20 Correct 2230 ms 154080 KB Output is correct
21 Correct 2115 ms 154080 KB Output is correct
22 Correct 2136 ms 154080 KB Output is correct
23 Correct 2096 ms 154160 KB Output is correct
24 Correct 1789 ms 154228 KB Output is correct
25 Correct 1794 ms 154476 KB Output is correct
26 Correct 1943 ms 154112 KB Output is correct
27 Correct 1900 ms 154108 KB Output is correct
28 Correct 1943 ms 154252 KB Output is correct
29 Correct 1970 ms 153984 KB Output is correct
30 Correct 1929 ms 154016 KB Output is correct
31 Correct 1959 ms 154092 KB Output is correct
32 Correct 1985 ms 154292 KB Output is correct
33 Correct 2001 ms 154072 KB Output is correct
34 Correct 1677 ms 154188 KB Output is correct
35 Correct 1687 ms 154336 KB Output is correct
36 Correct 1660 ms 154188 KB Output is correct
37 Correct 1675 ms 154284 KB Output is correct
38 Correct 1683 ms 154080 KB Output is correct
39 Correct 1689 ms 154128 KB Output is correct
40 Correct 1297 ms 142308 KB Output is correct
41 Correct 1648 ms 154024 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 125548 KB Output is correct
2 Correct 76 ms 125548 KB Output is correct
3 Correct 78 ms 125548 KB Output is correct
4 Correct 78 ms 125548 KB Output is correct
5 Correct 77 ms 125548 KB Output is correct
6 Correct 80 ms 125548 KB Output is correct
7 Correct 80 ms 125548 KB Output is correct
8 Correct 80 ms 125548 KB Output is correct
9 Correct 79 ms 125548 KB Output is correct
10 Correct 79 ms 125548 KB Output is correct
11 Correct 92 ms 125676 KB Output is correct
12 Correct 95 ms 126188 KB Output is correct
13 Correct 98 ms 126188 KB Output is correct
14 Correct 108 ms 126232 KB Output is correct
15 Correct 111 ms 126316 KB Output is correct
16 Correct 103 ms 126188 KB Output is correct
17 Correct 100 ms 126152 KB Output is correct
18 Correct 102 ms 126188 KB Output is correct
19 Runtime error 884 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -