| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1047938 | TAhmed33 | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int const mxN = 1e6+5;
int n, pw;
vector<int> seg [4*mxN];
int ans[4*mxN], a[4*mxN];
void build ( int node, int l, int r) {
if(l==r-1) { seg[node].push_back(a[l]); return; }
int m = (l+r)/2;
build(node*2+1, l, m) , build(node*2+2, m, r);
seg[node] = seg[node*2+1];
int maxi = seg[node].back();
for(auto it:seg[node*2+2]) seg[node].push_back(it);
sort(seg[node].begin(),seg[node].end());
int ind = lower_bound(seg[node*2+2].begin(), seg[node*2+2].end(), maxi) - seg[node*2+2].begin(); ind--;
if(ind<0) ans[node] = 0;
else { ans[node] = seg[node*2+2][ind] + maxi; }
ans[node] = max ({ans[node], ans[node*2+1], ans[node*2+2]});
}
int fin = 0, maxi = 0;
void get ( int node, int l_n, int r_n, int l, int r) {
if(l_n>=r || r_n<=l) return;
if(l<=l_n && r>=r_n) {
fin = max (fin, ans[node]);
int ind = lower_bound(seg[node].begin(), seg[node].end(), maxi) - seg[node].begin(); ind--;
if(ind>=0) {
fin = max ( fin, maxi+seg[node][ind]);
}
maxi = max ( maxi, seg[node].back());
return;
}
int m = (l_n+r_n) / 2;
get(node*2+1, l_n, m, l, r), get(node*2+2, m ,r_n, l, r);
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
cin>>n;
for(int i=0; i<n; i++) cin>>a[i];
pw = (1<<(__lg(n-1)+1));
build(0,0,pw);
int q; cin>>q;
while(q--) {
int x,y; cin>>x>>y; int k; cin >> k;
x--;
fin = 0, maxi = 0;
get(0,0,pw,x,y);
cout<<(fin <= k)<<'\n';
}
return 0;