oj.uz

Submission #1096631

# Submission time Handle Problem Language Result Execution time Memory
1096631 2024-10-04T22:53:22 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;

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].mx=max(seg[node*2+1].mx,seg[node*2+2].mx);
	ll mx=0;
	for(ll i=start;i<=end;++i){
		if(mx>ar[i]){
			seg[node].bad_mx=max(seg[node].bad_mx,mx+ar[i]);
		}else{
			mx=ar[i];
		}
	}
}

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:79:38: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   79 | Node left_right_mrg(Node lft,Node rgt){
      |                                      ^
sortbooks.cpp:79:38: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:79:38: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:79:38: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:101:35: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  101 | void build(ll node,ll start,ll end){
      |                                   ^
sortbooks.cpp:101:35: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:101:35: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:101:35: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:124:41: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  124 | Node qry(ll nd,ll start,ll end,ll l,ll r){
      |                                         ^
sortbooks.cpp:124:41: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:124:41: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:124:41: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:135:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  135 | void solve(){
      |            ^
sortbooks.cpp:135:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:135:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:135:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:149:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  149 | signed main() {
      |             ^
sortbooks.cpp:149:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:149:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:149: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 52 ms 159060 KB Output is correct
2 Correct 52 ms 159060 KB Output is correct
3 Correct 56 ms 159312 KB Output is correct
4 Correct 53 ms 159312 KB Output is correct
5 Correct 53 ms 159300 KB Output is correct
6 Correct 55 ms 159312 KB Output is correct
7 Correct 51 ms 159312 KB Output is correct
8 Correct 54 ms 159312 KB Output is correct
9 Correct 50 ms 159296 KB Output is correct
10 Correct 56 ms 159316 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 159060 KB Output is correct
2 Correct 52 ms 159060 KB Output is correct
3 Correct 56 ms 159312 KB Output is correct
4 Correct 53 ms 159312 KB Output is correct
5 Correct 53 ms 159300 KB Output is correct
6 Correct 55 ms 159312 KB Output is correct
7 Correct 51 ms 159312 KB Output is correct
8 Correct 54 ms 159312 KB Output is correct
9 Correct 50 ms 159296 KB Output is correct
10 Correct 56 ms 159316 KB Output is correct
11 Correct 80 ms 159652 KB Output is correct
12 Correct 125 ms 160532 KB Output is correct
13 Correct 151 ms 160536 KB Output is correct
14 Correct 189 ms 160588 KB Output is correct
15 Correct 218 ms 160572 KB Output is correct
16 Correct 194 ms 160576 KB Output is correct
17 Correct 82 ms 160012 KB Output is correct
18 Correct 139 ms 160572 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 265 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 3052 ms 184392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 159060 KB Output is correct
2 Correct 52 ms 159060 KB Output is correct
3 Correct 56 ms 159312 KB Output is correct
4 Correct 53 ms 159312 KB Output is correct
5 Correct 53 ms 159300 KB Output is correct
6 Correct 55 ms 159312 KB Output is correct
7 Correct 51 ms 159312 KB Output is correct
8 Correct 54 ms 159312 KB Output is correct
9 Correct 50 ms 159296 KB Output is correct
10 Correct 56 ms 159316 KB Output is correct
11 Correct 80 ms 159652 KB Output is correct
12 Correct 125 ms 160532 KB Output is correct
13 Correct 151 ms 160536 KB Output is correct
14 Correct 189 ms 160588 KB Output is correct
15 Correct 218 ms 160572 KB Output is correct
16 Correct 194 ms 160576 KB Output is correct
17 Correct 82 ms 160012 KB Output is correct
18 Correct 139 ms 160572 KB Output is correct
19 Execution timed out 3067 ms 210964 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 159060 KB Output is correct
2 Correct 52 ms 159060 KB Output is correct
3 Correct 56 ms 159312 KB Output is correct
4 Correct 53 ms 159312 KB Output is correct
5 Correct 53 ms 159300 KB Output is correct
6 Correct 55 ms 159312 KB Output is correct
7 Correct 51 ms 159312 KB Output is correct
8 Correct 54 ms 159312 KB Output is correct
9 Correct 50 ms 159296 KB Output is correct
10 Correct 56 ms 159316 KB Output is correct
11 Correct 80 ms 159652 KB Output is correct
12 Correct 125 ms 160532 KB Output is correct
13 Correct 151 ms 160536 KB Output is correct
14 Correct 189 ms 160588 KB Output is correct
15 Correct 218 ms 160572 KB Output is correct
16 Correct 194 ms 160576 KB Output is correct
17 Correct 82 ms 160012 KB Output is correct
18 Correct 139 ms 160572 KB Output is correct
19 Runtime error 265 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -