oj.uz

Submission #1096625

# Submission time Handle Problem Language Result Execution time Memory
1096625 2024-10-04T22:36:38 Z rayan_bd Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

#define getar(ar,n) for(ll i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ret return
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())

const int mxN = 1e6 + 50;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ld EPS = 1e-9;

struct Node{
	vector<ll> vec;
	ll mx=0,bad_mx=0;
};
Node seg[mxN*4];
ll ar[mxN];

Node dummy_node;


ll calc1(ll node){
	ll lft_max=seg[node*2+1].mx;
	ll ans=-lft_max,st=0,en=seg[node*2+2].vec.size()-1;
	while(st<=en){
		ll mid=st+(en-st)/2;
		if(seg[node*2+2].vec[mid]<lft_max){
			st=mid+1;
			ans=seg[node*2+2].vec[mid];
		}else{
			en=mid-1;
		}
	}
	return ans+lft_max;
}

Node left_right_mrg(Node lft,Node rgt){
	ll lft_max=lft.mx;
	ll ans=-lft_max,st=0,en=rgt.vec.size()-1;
	while(st<=en){
		ll mid=st+(en-st)/2;
		if(rgt.vec[mid]<lft_max){
			st=mid+1;
			ans=rgt.vec[mid];
		}else{
			en=mid-1;
		}
	}	
	ans+=lft_max;

	Node curr;
	curr.bad_mx=max({lft.bad_mx,ans,rgt.bad_mx});
	merge(all(lft.vec),all(rgt.vec),back_inserter(curr.vec));
	curr.mx=max(lft.mx,rgt.mx);

	return curr;
}

void build(ll node,ll start,ll end){
	if(start==end){
		seg[node].vec.pb(ar[start]);
		seg[node].mx=ar[start];
		seg[node].bad_mx=0;
		return;
	}
	ll mid=start+(end-start)/2;
	build(node*2+1,start,mid);
	build(node*2+2,mid+1,end);

	merge(all(seg[node*2+1].vec),all(seg[node*2+2].vec),back_inserter(seg[node].vec));
	seg[node].bad_mx=max({seg[node*2+1].bad_mx,seg[node*2+2].bad_mx,calc1(node)});
	seg[node].mx=max(seg[node*2+1].mx,seg[node*2+2].mx);
}

Node qry(ll nd,ll start,ll end,ll l,ll r){
	if(start>r||end<l) return dummy_node;
	if(start>=l&&end<=r) return seg[nd];
	ll mid=start+(end-start)/2;
	Node lft=qry(nd*2+1,start,mid,l,r);
	Node rgt=qry(nd*2+2,mid+1,end,l,r);
	if(lft.mx==-1) return rgt;
	else if(rgt.mx==-1) return lft;
	return left_right_mrg(lft,rgt);
}

void solve(){
	ll n,l,r,w,q;cin>>n>>q;
	for(ll i=0;i<n;++i){
		cin>>ar[i];
	}
	dummy_node.mx=-1;
	build(0,0,n-1);
	while(q--){
		cin>>l>>r>>w;
		cout<<(qry(0,0,n-1,l-1,r-1).bad_mx<=w)<<nl;
	}
}


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message

sortbooks.cpp:25:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   25 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
sortbooks.cpp:32:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
sortbooks.cpp:34:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   34 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
sortbooks.cpp:48:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   48 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
sortbooks.cpp:80:17: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   80 | ll calc1(ll node){
      |                 ^
sortbooks.cpp:80:17: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:80:17: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:80:17: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:95:38: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   95 | Node left_right_mrg(Node lft,Node rgt){
      |                                      ^
sortbooks.cpp:95:38: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:95:38: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:95:38: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:117:35: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  117 | void build(ll node,ll start,ll end){
      |                                   ^
sortbooks.cpp:117:35: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:117:35: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:117:35: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:133:41: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  133 | Node qry(ll nd,ll start,ll end,ll l,ll r){
      |                                         ^
sortbooks.cpp:133:41: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:133:41: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:133:41: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:144:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  144 | void solve(){
      |            ^
sortbooks.cpp:144:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:144:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:144:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:158:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  158 | signed main() {
      |             ^
sortbooks.cpp:158:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:158:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:158:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 158348 KB Output is correct
2 Correct 53 ms 158524 KB Output is correct
3 Correct 51 ms 158504 KB Output is correct
4 Correct 52 ms 158288 KB Output is correct
5 Correct 55 ms 158544 KB Output is correct
6 Correct 54 ms 158544 KB Output is correct
7 Correct 53 ms 158404 KB Output is correct
8 Correct 53 ms 158616 KB Output is correct
9 Correct 54 ms 158544 KB Output is correct
10 Correct 54 ms 158548 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 158348 KB Output is correct
2 Correct 53 ms 158524 KB Output is correct
3 Correct 51 ms 158504 KB Output is correct
4 Correct 52 ms 158288 KB Output is correct
5 Correct 55 ms 158544 KB Output is correct
6 Correct 54 ms 158544 KB Output is correct
7 Correct 53 ms 158404 KB Output is correct
8 Correct 53 ms 158616 KB Output is correct
9 Correct 54 ms 158544 KB Output is correct
10 Correct 54 ms 158548 KB Output is correct
11 Correct 75 ms 158804 KB Output is correct
12 Correct 128 ms 159704 KB Output is correct
13 Correct 136 ms 159728 KB Output is correct
14 Correct 195 ms 159748 KB Output is correct
15 Correct 197 ms 159760 KB Output is correct
16 Correct 181 ms 159760 KB Output is correct
17 Correct 79 ms 159292 KB Output is correct
18 Correct 132 ms 159756 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 243 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 158348 KB Output is correct
2 Correct 53 ms 158524 KB Output is correct
3 Correct 51 ms 158504 KB Output is correct
4 Correct 52 ms 158288 KB Output is correct
5 Correct 55 ms 158544 KB Output is correct
6 Correct 54 ms 158544 KB Output is correct
7 Correct 53 ms 158404 KB Output is correct
8 Correct 53 ms 158616 KB Output is correct
9 Correct 54 ms 158544 KB Output is correct
10 Correct 54 ms 158548 KB Output is correct
11 Correct 75 ms 158804 KB Output is correct
12 Correct 128 ms 159704 KB Output is correct
13 Correct 136 ms 159728 KB Output is correct
14 Correct 195 ms 159748 KB Output is correct
15 Correct 197 ms 159760 KB Output is correct
16 Correct 181 ms 159760 KB Output is correct
17 Correct 79 ms 159292 KB Output is correct
18 Correct 132 ms 159756 KB Output is correct
19 Execution timed out 3068 ms 210224 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 158348 KB Output is correct
2 Correct 53 ms 158524 KB Output is correct
3 Correct 51 ms 158504 KB Output is correct
4 Correct 52 ms 158288 KB Output is correct
5 Correct 55 ms 158544 KB Output is correct
6 Correct 54 ms 158544 KB Output is correct
7 Correct 53 ms 158404 KB Output is correct
8 Correct 53 ms 158616 KB Output is correct
9 Correct 54 ms 158544 KB Output is correct
10 Correct 54 ms 158548 KB Output is correct
11 Correct 75 ms 158804 KB Output is correct
12 Correct 128 ms 159704 KB Output is correct
13 Correct 136 ms 159728 KB Output is correct
14 Correct 195 ms 159748 KB Output is correct
15 Correct 197 ms 159760 KB Output is correct
16 Correct 181 ms 159760 KB Output is correct
17 Correct 79 ms 159292 KB Output is correct
18 Correct 132 ms 159756 KB Output is correct
19 Runtime error 243 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -