oj.uz

Submission #154102

# Submission time Handle Problem Language Result Execution time Memory
154102 2019-09-18T11:14:09 Z beso123 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 3000 ms 163460 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int mas[4000001];
int T[1000001];
int mx[1000001];
int mn[1000001];
int R[1000001];
vector <int> v[4000001];
void buildM (int p,int tl,int tr){
	if (tl==tr){
		mn[p]=R[tl];
		return ;
	}
	int mid=tl+tr>>1;
	buildM(p+p,tl,mid);
	buildM(p+p+1,mid+1,tr);
	
	mn[p]=min(mn[2*p],mn[2*p+1]);
}
int findM (int p,int tl,int tr,int l,int r){
	if(l>r) return 0;
	if (l<=tl&&tr<=r){
		return mn[p];
	}
	
	if (tl>r||l>tr){
		return 0;
	}
	
	int mid= tl+tr>>1;
	int a=findM(p+p,tl,mid,l,r);
	int b=findM(p+p+1,mid+1,tr,l,r);
	return min(a,b);
}
void build (int p,int tl,int tr){
	if (tl==tr){
		v[p].push_back(mas[tl]);
		mx[p]=mas[tl];
		T[p]=0;
		return ;
	}
	int mid=tl+tr>>1;
	build(p+p,tl,mid);
	build(p+p+1,mid+1,tr);
	
	int e=0,i=0;
	while (e<v[2*p+1].size()||i<v[2*p].size()){
		if (e==v[2*p+1].size()){
			v[p].push_back(v[2*p][i]);
			i++;
			continue;
		}
		if (i==v[2*p].size()){
			v[p].push_back(v[2*p+1][e]);
			e++;
			continue;
		}
		if (v[2*p+1][e]<v[2*p][i]){
			v[p].push_back(v[2*p+1][e]);
			e++;
		}
		else{
			v[p].push_back(v[2*p][i]);
			i++;
		}
	}
	//cout<<p<<" "<<v[p].size()<<endl;
	int MAX=0;
	for (int i=tl;i<=tr;i++){
		if (mas[i]<MAX){
			T[p]=max(T[p],MAX+mas[i]);
		}
		MAX=max(mas[i],MAX);
	}
	
	mx[p]=max(mx[2*p],mx[2*p+1]);
}
int CURMAX=0;
int find (int p,int tl,int tr,int l,int r){
	if (l<=tl&&tr<=r){
		int beg=0,en=v[p].size()-1,as=-1;
		while (beg<=en){
			int mid=(beg+en>>1);
			if(v[p][mid]>=CURMAX){
				en=mid-1;
			}
			else{
				beg=mid+1;
				as=mid;
			}
		}
		int ke;
		int e=CURMAX;
		CURMAX=max(CURMAX,mx[p]);
		if (as==-1) return T[p]; 
			else ke=max(T[p],e+v[p][as]);
		return ke;
	}
	
	if (tl>r||l>tr){
		return 0;
	}
	
	int mid= tl+tr>>1;
	int a=find(p+p,tl,mid,l,r);
	int b=find(p+p+1,mid+1,tr,l,r);
	return max(a,b);
}
int t;
int l[1000001],r[1000001],x[1000001];
set <pair <int,int> > s;
main (){
	ios_base::sync_with_stdio(false);
	cin>>n>>t;
	int MIN=1000000000000;
	for (int i=1;i<=n;i++){
		cin>>mas[i];
		MIN=min(MIN,mas[i]);
	}
	
	bool ok=true;
	for (int i=1;i<=t;i++){
		cin>>l[i]>>r[i]>>x[i];
		CURMAX=0;
		if (x[i]>MIN){
			ok=false;
		}
	}
	
	if (ok){
		for (int i=1;i<=n;i++){
			if(mas[i]>mas[i+1]){
				R[i+1]=-1;
			}
		}
		buildM(1,1,n);
		for (int i=1;i<=t;i++){
			CURMAX=0;
			int wow=findM (1,1,n,l[i]+1,r[i]);
			cout<<(wow!=-1)<<endl;
		}
	}
	else{
		
		build (1,1,n);
		for (int i=1;i<=t;i++){
			CURMAX=0;
			int wow=find (1,1,n,l[i],r[i]);
			cout<<(wow<=x[i])<<endl;
		}
	}
	return 0;
}

Compilation message

sortbooks.cpp: In function 'void buildM(long long int, long long int, long long int)':
sortbooks.cpp:16:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sortbooks.cpp: In function 'long long int findM(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:32:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid= tl+tr>>1;
           ~~^~~
sortbooks.cpp: In function 'void build(long long int, long long int, long long int)':
sortbooks.cpp:44:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sortbooks.cpp:49:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (e<v[2*p+1].size()||i<v[2*p].size()){
         ~^~~~~~~~~~~~~~~~
sortbooks.cpp:49:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (e<v[2*p+1].size()||i<v[2*p].size()){
                            ~^~~~~~~~~~~~~~
sortbooks.cpp:50:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (e==v[2*p+1].size()){
       ~^~~~~~~~~~~~~~~~~
sortbooks.cpp:55:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i==v[2*p].size()){
       ~^~~~~~~~~~~~~~~
sortbooks.cpp: In function 'long long int find(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:85:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=(beg+en>>1);
             ~~~^~~
sortbooks.cpp:106:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid= tl+tr>>1;
           ~~^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:114:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main (){
       ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 94328 KB Output is correct
2 Correct 94 ms 94328 KB Output is correct
3 Correct 108 ms 94328 KB Output is correct
4 Correct 90 ms 94328 KB Output is correct
5 Correct 99 ms 94372 KB Output is correct
6 Correct 96 ms 94584 KB Output is correct
7 Correct 108 ms 94456 KB Output is correct
8 Correct 97 ms 94548 KB Output is correct
9 Correct 90 ms 94456 KB Output is correct
10 Correct 92 ms 94532 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 94328 KB Output is correct
2 Correct 94 ms 94328 KB Output is correct
3 Correct 108 ms 94328 KB Output is correct
4 Correct 90 ms 94328 KB Output is correct
5 Correct 99 ms 94372 KB Output is correct
6 Correct 96 ms 94584 KB Output is correct
7 Correct 108 ms 94456 KB Output is correct
8 Correct 97 ms 94548 KB Output is correct
9 Correct 90 ms 94456 KB Output is correct
10 Correct 92 ms 94532 KB Output is correct
11 Correct 106 ms 94848 KB Output is correct
12 Correct 103 ms 95836 KB Output is correct
13 Correct 111 ms 95836 KB Output is correct
14 Correct 125 ms 95980 KB Output is correct
15 Correct 113 ms 95836 KB Output is correct
16 Correct 111 ms 96016 KB Output is correct
17 Correct 108 ms 95240 KB Output is correct
18 Correct 108 ms 95736 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 163460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 124780 KB Output is correct
2 Correct 679 ms 124912 KB Output is correct
3 Correct 634 ms 124348 KB Output is correct
4 Correct 669 ms 124520 KB Output is correct
5 Correct 645 ms 124400 KB Output is correct
6 Correct 556 ms 124192 KB Output is correct
7 Correct 542 ms 124144 KB Output is correct
8 Correct 584 ms 124016 KB Output is correct
9 Correct 409 ms 98424 KB Output is correct
10 Correct 644 ms 124020 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 94328 KB Output is correct
2 Correct 94 ms 94328 KB Output is correct
3 Correct 108 ms 94328 KB Output is correct
4 Correct 90 ms 94328 KB Output is correct
5 Correct 99 ms 94372 KB Output is correct
6 Correct 96 ms 94584 KB Output is correct
7 Correct 108 ms 94456 KB Output is correct
8 Correct 97 ms 94548 KB Output is correct
9 Correct 90 ms 94456 KB Output is correct
10 Correct 92 ms 94532 KB Output is correct
11 Correct 106 ms 94848 KB Output is correct
12 Correct 103 ms 95836 KB Output is correct
13 Correct 111 ms 95836 KB Output is correct
14 Correct 125 ms 95980 KB Output is correct
15 Correct 113 ms 95836 KB Output is correct
16 Correct 111 ms 96016 KB Output is correct
17 Correct 108 ms 95240 KB Output is correct
18 Correct 108 ms 95736 KB Output is correct
19 Correct 1381 ms 156708 KB Output is correct
20 Correct 1492 ms 156732 KB Output is correct
21 Correct 1235 ms 159340 KB Output is correct
22 Correct 1227 ms 159304 KB Output is correct
23 Correct 1235 ms 159300 KB Output is correct
24 Correct 1107 ms 158188 KB Output is correct
25 Correct 1102 ms 158244 KB Output is correct
26 Correct 1210 ms 158448 KB Output is correct
27 Correct 1220 ms 158332 KB Output is correct
28 Correct 1299 ms 158264 KB Output is correct
29 Correct 1291 ms 158500 KB Output is correct
30 Correct 1276 ms 158360 KB Output is correct
31 Correct 1273 ms 158448 KB Output is correct
32 Correct 1281 ms 158408 KB Output is correct
33 Correct 1273 ms 158456 KB Output is correct
34 Correct 1061 ms 157988 KB Output is correct
35 Correct 1077 ms 158056 KB Output is correct
36 Correct 1051 ms 157804 KB Output is correct
37 Correct 1044 ms 157840 KB Output is correct
38 Correct 1051 ms 158132 KB Output is correct
39 Correct 1194 ms 157448 KB Output is correct
40 Correct 992 ms 132352 KB Output is correct
41 Correct 1138 ms 156640 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 94328 KB Output is correct
2 Correct 94 ms 94328 KB Output is correct
3 Correct 108 ms 94328 KB Output is correct
4 Correct 90 ms 94328 KB Output is correct
5 Correct 99 ms 94372 KB Output is correct
6 Correct 96 ms 94584 KB Output is correct
7 Correct 108 ms 94456 KB Output is correct
8 Correct 97 ms 94548 KB Output is correct
9 Correct 90 ms 94456 KB Output is correct
10 Correct 92 ms 94532 KB Output is correct
11 Correct 106 ms 94848 KB Output is correct
12 Correct 103 ms 95836 KB Output is correct
13 Correct 111 ms 95836 KB Output is correct
14 Correct 125 ms 95980 KB Output is correct
15 Correct 113 ms 95836 KB Output is correct
16 Correct 111 ms 96016 KB Output is correct
17 Correct 108 ms 95240 KB Output is correct
18 Correct 108 ms 95736 KB Output is correct
19 Execution timed out 3073 ms 163460 KB Time limit exceeded
20 Halted 0 ms 0 KB -