oj.uz

Submission #1047316

# Submission time Handle Problem Language Result Execution time Memory
1047316 2024-08-07T11:55:45 Z vjudge1 Index (COCI21_index) C++14
110 / 110
 2261 ms 56788 KB 
#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;
	}
	
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29652 KB Output is correct
2 Correct 7 ms 29532 KB Output is correct
3 Correct 7 ms 29532 KB Output is correct
4 Correct 7 ms 29532 KB Output is correct
5 Correct 11 ms 29528 KB Output is correct
6 Correct 7 ms 29532 KB Output is correct
7 Correct 7 ms 29532 KB Output is correct
8 Correct 7 ms 29532 KB Output is correct
9 Correct 8 ms 29672 KB Output is correct
10 Correct 7 ms 29532 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29652 KB Output is correct
2 Correct 7 ms 29532 KB Output is correct
3 Correct 7 ms 29532 KB Output is correct
4 Correct 7 ms 29532 KB Output is correct
5 Correct 11 ms 29528 KB Output is correct
6 Correct 7 ms 29532 KB Output is correct
7 Correct 7 ms 29532 KB Output is correct
8 Correct 7 ms 29532 KB Output is correct
9 Correct 8 ms 29672 KB Output is correct
10 Correct 7 ms 29532 KB Output is correct
11 Correct 396 ms 36176 KB Output is correct
12 Correct 389 ms 36272 KB Output is correct
13 Correct 397 ms 36176 KB Output is correct
14 Correct 403 ms 36180 KB Output is correct
15 Correct 390 ms 36180 KB Output is correct
16 Correct 392 ms 36176 KB Output is correct
17 Correct 404 ms 36168 KB Output is correct
18 Correct 400 ms 36176 KB Output is correct
19 Correct 398 ms 36436 KB Output is correct
20 Correct 428 ms 36184 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29652 KB Output is correct
2 Correct 7 ms 29532 KB Output is correct
3 Correct 7 ms 29532 KB Output is correct
4 Correct 7 ms 29532 KB Output is correct
5 Correct 11 ms 29528 KB Output is correct
6 Correct 7 ms 29532 KB Output is correct
7 Correct 7 ms 29532 KB Output is correct
8 Correct 7 ms 29532 KB Output is correct
9 Correct 8 ms 29672 KB Output is correct
10 Correct 7 ms 29532 KB Output is correct
11 Correct 396 ms 36176 KB Output is correct
12 Correct 389 ms 36272 KB Output is correct
13 Correct 397 ms 36176 KB Output is correct
14 Correct 403 ms 36180 KB Output is correct
15 Correct 390 ms 36180 KB Output is correct
16 Correct 392 ms 36176 KB Output is correct
17 Correct 404 ms 36168 KB Output is correct
18 Correct 400 ms 36176 KB Output is correct
19 Correct 398 ms 36436 KB Output is correct
20 Correct 428 ms 36184 KB Output is correct
21 Correct 2261 ms 56768 KB Output is correct
22 Correct 2240 ms 56692 KB Output is correct
23 Correct 2171 ms 56628 KB Output is correct
24 Correct 2090 ms 56708 KB Output is correct
25 Correct 2102 ms 56788 KB Output is correct
26 Correct 2110 ms 56656 KB Output is correct
27 Correct 2131 ms 56660 KB Output is correct
28 Correct 2094 ms 56668 KB Output is correct
29 Correct 2078 ms 56716 KB Output is correct
30 Correct 2080 ms 56620 KB Output is correct