oj.uz

Submission #1096635

# Submission time Handle Problem Language Result Execution time Memory
1096635 2024-10-04T23:07:50 Z rayan_bd Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 277 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*2];
ll ar[mxN],mx=0;

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);

	seg[node].vec.assign(seg[node*2+1].vec.size()+seg[node*2+2].vec.size(),0);
	merge(all(seg[node*2+1].vec),all(seg[node*2+2].vec),seg[node].vec.begin());
	seg[node].mx=max(seg[node*2+1].mx,seg[node*2+2].mx);
	ll mxx=0;
	for(ll i=start;i<=end;++i){
		if(mxx>ar[i]){
			seg[node].bad_mx=max(seg[node].bad_mx,mxx+ar[i]);
		}else{
			mxx=ar[i];
		}
	}
}

bool qry(ll nd,ll start,ll end,ll l,ll r,ll k){
	if(start>r||end<l) return 1;
	if(start>=l&&end<=r){
		bool f=(max(seg[nd].bad_mx,(mx>seg[nd].vec[0]?mx+*--lower_bound(all(seg[nd].vec),mx):0))<=k);
		mx=max(mx,seg[nd].mx);
		return f;
	}
	ll mid=start+(end-start)/2;
	return ((!qry(nd*2+1,start,mid,l,r,k)||!qry(nd*2+2,mid+1,end,l,r,k))?0:1);
}

void solve(){
	ll n,l,r,w,q;cin>>n>>q;
	for(ll i=0;i<n;++i){
		cin>>ar[i];
	}
	build(0,0,n-1);
	while(q--){
		cin>>l>>r>>w;
		mx=0;
		cout<<(qry(0,0,n-1,l-1,r-1,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:77:35: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   77 | void build(ll node,ll start,ll end){
      |                                   ^
sortbooks.cpp:77:35: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:77:35: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:77:35: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:101:46: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  101 | bool qry(ll nd,ll start,ll end,ll l,ll r,ll k){
      |                                              ^
sortbooks.cpp:101:46: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:101:46: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:101:46: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:112:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  112 | void solve(){
      |            ^
sortbooks.cpp:112:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:112:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:112:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:126:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  126 | signed main() {
      |             ^
sortbooks.cpp:126:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:126:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:126: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 28 ms 80476 KB Output is correct
2 Correct 26 ms 80476 KB Output is correct
3 Correct 28 ms 80464 KB Output is correct
4 Correct 27 ms 80476 KB Output is correct
5 Correct 27 ms 80692 KB Output is correct
6 Correct 27 ms 80732 KB Output is correct
7 Correct 33 ms 80732 KB Output is correct
8 Correct 33 ms 80504 KB Output is correct
9 Correct 28 ms 80468 KB Output is correct
10 Correct 28 ms 80464 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 80476 KB Output is correct
2 Correct 26 ms 80476 KB Output is correct
3 Correct 28 ms 80464 KB Output is correct
4 Correct 27 ms 80476 KB Output is correct
5 Correct 27 ms 80692 KB Output is correct
6 Correct 27 ms 80732 KB Output is correct
7 Correct 33 ms 80732 KB Output is correct
8 Correct 33 ms 80504 KB Output is correct
9 Correct 28 ms 80468 KB Output is correct
10 Correct 28 ms 80464 KB Output is correct
11 Correct 26 ms 80984 KB Output is correct
12 Correct 33 ms 81240 KB Output is correct
13 Correct 32 ms 81236 KB Output is correct
14 Correct 28 ms 81500 KB Output is correct
15 Correct 28 ms 81496 KB Output is correct
16 Correct 30 ms 81492 KB Output is correct
17 Correct 28 ms 81244 KB Output is correct
18 Correct 35 ms 81240 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 101076 KB Output is correct
2 Correct 98 ms 100824 KB Output is correct
3 Correct 107 ms 100692 KB Output is correct
4 Correct 122 ms 100696 KB Output is correct
5 Correct 103 ms 100688 KB Output is correct
6 Correct 83 ms 100760 KB Output is correct
7 Correct 81 ms 100692 KB Output is correct
8 Correct 88 ms 100508 KB Output is correct
9 Correct 50 ms 82000 KB Output is correct
10 Correct 92 ms 100436 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 80476 KB Output is correct
2 Correct 26 ms 80476 KB Output is correct
3 Correct 28 ms 80464 KB Output is correct
4 Correct 27 ms 80476 KB Output is correct
5 Correct 27 ms 80692 KB Output is correct
6 Correct 27 ms 80732 KB Output is correct
7 Correct 33 ms 80732 KB Output is correct
8 Correct 33 ms 80504 KB Output is correct
9 Correct 28 ms 80468 KB Output is correct
10 Correct 28 ms 80464 KB Output is correct
11 Correct 26 ms 80984 KB Output is correct
12 Correct 33 ms 81240 KB Output is correct
13 Correct 32 ms 81236 KB Output is correct
14 Correct 28 ms 81500 KB Output is correct
15 Correct 28 ms 81496 KB Output is correct
16 Correct 30 ms 81492 KB Output is correct
17 Correct 28 ms 81244 KB Output is correct
18 Correct 35 ms 81240 KB Output is correct
19 Correct 249 ms 124500 KB Output is correct
20 Correct 251 ms 124408 KB Output is correct
21 Correct 201 ms 124244 KB Output is correct
22 Correct 196 ms 124240 KB Output is correct
23 Correct 202 ms 124424 KB Output is correct
24 Correct 190 ms 123988 KB Output is correct
25 Correct 178 ms 124228 KB Output is correct
26 Correct 199 ms 124268 KB Output is correct
27 Correct 204 ms 124244 KB Output is correct
28 Correct 226 ms 124240 KB Output is correct
29 Correct 225 ms 124244 KB Output is correct
30 Correct 242 ms 124244 KB Output is correct
31 Correct 219 ms 124244 KB Output is correct
32 Correct 243 ms 124244 KB Output is correct
33 Correct 245 ms 124428 KB Output is correct
34 Correct 176 ms 123988 KB Output is correct
35 Correct 163 ms 123984 KB Output is correct
36 Correct 166 ms 123728 KB Output is correct
37 Correct 168 ms 123728 KB Output is correct
38 Correct 168 ms 118864 KB Output is correct
39 Correct 185 ms 118872 KB Output is correct
40 Correct 150 ms 105652 KB Output is correct
41 Correct 167 ms 118864 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 80476 KB Output is correct
2 Correct 26 ms 80476 KB Output is correct
3 Correct 28 ms 80464 KB Output is correct
4 Correct 27 ms 80476 KB Output is correct
5 Correct 27 ms 80692 KB Output is correct
6 Correct 27 ms 80732 KB Output is correct
7 Correct 33 ms 80732 KB Output is correct
8 Correct 33 ms 80504 KB Output is correct
9 Correct 28 ms 80468 KB Output is correct
10 Correct 28 ms 80464 KB Output is correct
11 Correct 26 ms 80984 KB Output is correct
12 Correct 33 ms 81240 KB Output is correct
13 Correct 32 ms 81236 KB Output is correct
14 Correct 28 ms 81500 KB Output is correct
15 Correct 28 ms 81496 KB Output is correct
16 Correct 30 ms 81492 KB Output is correct
17 Correct 28 ms 81244 KB Output is correct
18 Correct 35 ms 81240 KB Output is correct
19 Runtime error 277 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -