| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 343674 | Bill_00 | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 100000000000000000
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pp push
#define M 1000001
typedef long long ll;
using namespace std;
struct node{
int ans;
vector<int>vec;
};
node a[4*M];
int s[M];
void build(int id,int l,int r){
if(l==r){
a[id].ans=-1e9;
a[id].vec.pb(s[l]);
return;
}
int m=l+r>>1;
build(id*2,l,m);
build(id*2+1,m+1,r);
if(a[id*2].vec[a[id*2].vec.size()-1]<=a[id*2+1].vec[0]){
a[id].ans=max(a[id*2].ans,a[id*2+1].ans);
}
else{
int ii=(lower_bound(a[id*2+1].vec.begin(),a[id*2+1].vec.end(),a[id*2].vec[a[id*2].vec.size()-1])-a[id*2+1].vec.begin());
a[id].ans=max(max(a[id*2].ans,a[id*2+1].ans),a[id*2].vec[a[id*2].vec.size()-1]+a[id*2+1].vec[ii-1]);
}
int i=0,j=0;
while(i<a[id*2].vec.size() && j<a[id*2+1].vec.size()){
if(a[id*2].vec[i]>a[id*2+1].vec[j]){
a[id].vec.pb(a[id*2+1].vec[j]);
j++;
}
else{
a[id].vec.pb(a[id*2].vec[i]);
i++;
}
}
while(i<a[id*2].vec.size()){
a[id].vec.pb(a[id*2].vec[i]);
i++;
}
while(j<a[id*2+1].vec.size()){
a[id].vec.pb(a[id*2+1].vec[j]);
j++;
}
}
int query1(int id,int l,int r,int L,int R){
if(r<L || R<l){
return -1e9;
}
if(L<=l && r<=R){
return a[id].vec[a[id].vec.size()-1];
}
int m=l+r>>1;
return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R));
}
int query2(int id,int l,int r,int L,int R,int k){
if(r<L || R<l){
return -1e9;
}
if(L<=l && r<=R){
if(a[id].vec[0]>=k) return -1e9;
else{
int ii=(lower_bound(a[id].vec.begin(),a[id].vec.end(),k)-a[id].vec.begin());
return a[id].vec[ii-1];
}
}
int m=l+r>>1;
return max(query2(id*2,l,m,L,R,k),query2(id*2+1,m+1,r,L,R,k));
}
int query(int id,int l,int r,int L,int R){
// cout << id << '\n';
if(r<L || R<l){
return -1e9;
}
if(L<=l && r<=R){
return a[id].ans;
}
int m=l+r>>1;
int b=query1(id*2,l,m,L,R);
int c=query2(id*2+1,m+1,r,L,R,b);
// cout << id << ' ' << b << ' ' << c << '\n';
return max(max(query(id*2,l,m,L,R),query(id*2+1,m+1,r,L,R)),b+c);
}
int main(){
// ios_base::sync_with_stdio(NULL);
// cin.tie(NULL);
// cout.tie(NULL);
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> s[i];
}
build(1,1,n);
for(int i=1;i<=m;i++){
int l,r,k;
cin >> l >> r;
if(k>=query(1,1,n,l,r).ans) cout << 1 << '\n';
else cout << 0 << '\n';
}
}