이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 300005
#define fi first
#define se second
#define sp " "
#define pb push_back
typedef int lo;
const int inf = 1e9+7;
vector<lo> mt[4*MAXN];
int n,k,q;
int arr[MAXN];
inline void build(int node, int start, int end)
{
if(start == end)
{
mt[node].pb(arr[start]);
return;
}
int mid = (start+end)/2;
build(node*2,start,mid);
build(node*2+1,mid+1,end);
mt[node].resize(mt[node*2].size()+mt[node*2+1].size());
merge(mt[node*2].begin(),mt[node*2].end(),mt[node*2+1].begin(),mt[node*2+1].end(),mt[node].begin());
}
inline int query(int node, int start, int end,int l,int r,int val)
{
if(start > end or start > r or end < l)
{
return 0;
}
if(start >= l and end <= r)
{
int a = lower_bound(mt[node].begin(),mt[node].end(),val) - mt[node].begin();
return mt[node].size()-a;
}
int mid = (start+end)/2;
return query(node*2,start,mid,l,r,val) + query(node*2+1,mid+1,end,l,r,val);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin >> n >> q;;
for (int i = 1; i <= n; ++i)
{
cin >> arr[i];
}
build(1,1,n);
while(q--)
{
int l,r;
cin >> l >> r;
lo bas = 0;
lo son = 1000000;
while(bas <= son)
{
lo mid = (bas+son)/2;
//~ cout << mid << sp << query(1,1,n,l,r,mid) << endl;
if(query(1,1,n,l,r,mid) >= mid)
{
bas = mid+1;
}
else
{
son = mid-1;
}
}
cout << son << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |