oj.uz

Submission #1096630

# Submission time Handle Problem Language Result Execution time Memory
1096630 2024-10-04T22:47:23 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 + 5000;
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 159060 KB Output is correct
2 Correct 53 ms 159304 KB Output is correct
3 Correct 55 ms 159312 KB Output is correct
4 Correct 50 ms 159316 KB Output is correct
5 Correct 52 ms 159312 KB Output is correct
6 Correct 55 ms 159312 KB Output is correct
7 Correct 56 ms 159312 KB Output is correct
8 Correct 57 ms 159312 KB Output is correct
9 Correct 53 ms 159316 KB Output is correct
10 Correct 53 ms 159312 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 159060 KB Output is correct
2 Correct 53 ms 159304 KB Output is correct
3 Correct 55 ms 159312 KB Output is correct
4 Correct 50 ms 159316 KB Output is correct
5 Correct 52 ms 159312 KB Output is correct
6 Correct 55 ms 159312 KB Output is correct
7 Correct 56 ms 159312 KB Output is correct
8 Correct 57 ms 159312 KB Output is correct
9 Correct 53 ms 159316 KB Output is correct
10 Correct 53 ms 159312 KB Output is correct
11 Correct 72 ms 159572 KB Output is correct
12 Correct 129 ms 160528 KB Output is correct
13 Correct 144 ms 160632 KB Output is correct
14 Correct 188 ms 160560 KB Output is correct
15 Correct 205 ms 160564 KB Output is correct
16 Correct 183 ms 160744 KB Output is correct
17 Correct 79 ms 160084 KB Output is correct
18 Correct 144 ms 160576 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 247 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 3034 ms 184488 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 159060 KB Output is correct
2 Correct 53 ms 159304 KB Output is correct
3 Correct 55 ms 159312 KB Output is correct
4 Correct 50 ms 159316 KB Output is correct
5 Correct 52 ms 159312 KB Output is correct
6 Correct 55 ms 159312 KB Output is correct
7 Correct 56 ms 159312 KB Output is correct
8 Correct 57 ms 159312 KB Output is correct
9 Correct 53 ms 159316 KB Output is correct
10 Correct 53 ms 159312 KB Output is correct
11 Correct 72 ms 159572 KB Output is correct
12 Correct 129 ms 160528 KB Output is correct
13 Correct 144 ms 160632 KB Output is correct
14 Correct 188 ms 160560 KB Output is correct
15 Correct 205 ms 160564 KB Output is correct
16 Correct 183 ms 160744 KB Output is correct
17 Correct 79 ms 160084 KB Output is correct
18 Correct 144 ms 160576 KB Output is correct
19 Execution timed out 3049 ms 210968 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 159060 KB Output is correct
2 Correct 53 ms 159304 KB Output is correct
3 Correct 55 ms 159312 KB Output is correct
4 Correct 50 ms 159316 KB Output is correct
5 Correct 52 ms 159312 KB Output is correct
6 Correct 55 ms 159312 KB Output is correct
7 Correct 56 ms 159312 KB Output is correct
8 Correct 57 ms 159312 KB Output is correct
9 Correct 53 ms 159316 KB Output is correct
10 Correct 53 ms 159312 KB Output is correct
11 Correct 72 ms 159572 KB Output is correct
12 Correct 129 ms 160528 KB Output is correct
13 Correct 144 ms 160632 KB Output is correct
14 Correct 188 ms 160560 KB Output is correct
15 Correct 205 ms 160564 KB Output is correct
16 Correct 183 ms 160744 KB Output is correct
17 Correct 79 ms 160084 KB Output is correct
18 Correct 144 ms 160576 KB Output is correct
19 Runtime error 247 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -