oj.uz

Submission #1046985

# Submission time Handle Problem Language Result Execution time Memory
1046985 2024-08-07T07:20:34 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 2201 ms 64952 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define MAX 1000000007
#define LLMAX 1000000000000000000
#define N 200005
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed<<setprecision(1)

int n,q,a[N];
vector<int> st[4*N];
int bs(int x,int val){
	int l=0,r=st[x].size();
	while(l<r){
		int mid=(l+r)/2;
		if(st[x][mid]>=val) r=mid;
		else l=mid+1;
	}
	return st[x].size()-l;
}
void build(){
	int l=n+1,r=2*n;
	for(int i=l;i<=r;i++) st[i].pb(a[i-n]);
	l/=2;
	r/=2;
	while(r>0){
		for(int i=max(l,(int)1);i<=r;i++){
			for(auto j:st[2*i]) st[i].pb(j);
			for(auto j:st[2*i+1]) st[i].pb(j);
			sort(all(st[i]));
		}
		l/=2;
		r/=2;
	}
}
int query(int l,int r,int val){
	l+=n;
	r+=n;
	int ans=0;
	while(l<=r){
		if(l&1){
			ans+=bs(l,val);
			l++;
		}
		if(!(r&1)){
			ans+=bs(r,val);
			r--;
		}
		l/=2;
		r/=2;
	}
	return ans;
}

int32_t main(){
	fast;
	cin >> n >> q;
	for(int i=1;i<=n;i++) cin >> a[i];
	build();
	while(q--){
		int x,y;
		cin >> x >> y;
		int l=1,r=y-x+1;
		while(l<r){
			int mid=(l+r+1)/2;
			if(query(x,y,mid)>=mid) l=mid;
			else r=mid-1;
		}
		cout << l << endl;
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19548 KB Output is correct
2 Correct 4 ms 19348 KB Output is correct
3 Correct 4 ms 19292 KB Output is correct
4 Correct 4 ms 19292 KB Output is correct
5 Correct 4 ms 19292 KB Output is correct
6 Correct 4 ms 19412 KB Output is correct
7 Correct 4 ms 19292 KB Output is correct
8 Correct 4 ms 19292 KB Output is correct
9 Correct 4 ms 19292 KB Output is correct
10 Correct 4 ms 19292 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19548 KB Output is correct
2 Correct 4 ms 19348 KB Output is correct
3 Correct 4 ms 19292 KB Output is correct
4 Correct 4 ms 19292 KB Output is correct
5 Correct 4 ms 19292 KB Output is correct
6 Correct 4 ms 19412 KB Output is correct
7 Correct 4 ms 19292 KB Output is correct
8 Correct 4 ms 19292 KB Output is correct
9 Correct 4 ms 19292 KB Output is correct
10 Correct 4 ms 19292 KB Output is correct
11 Correct 349 ms 29508 KB Output is correct
12 Correct 343 ms 29512 KB Output is correct
13 Correct 341 ms 29772 KB Output is correct
14 Correct 345 ms 29508 KB Output is correct
15 Correct 356 ms 29508 KB Output is correct
16 Correct 351 ms 29776 KB Output is correct
17 Correct 360 ms 29904 KB Output is correct
18 Correct 361 ms 29772 KB Output is correct
19 Correct 339 ms 29744 KB Output is correct
20 Correct 344 ms 29708 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19548 KB Output is correct
2 Correct 4 ms 19348 KB Output is correct
3 Correct 4 ms 19292 KB Output is correct
4 Correct 4 ms 19292 KB Output is correct
5 Correct 4 ms 19292 KB Output is correct
6 Correct 4 ms 19412 KB Output is correct
7 Correct 4 ms 19292 KB Output is correct
8 Correct 4 ms 19292 KB Output is correct
9 Correct 4 ms 19292 KB Output is correct
10 Correct 4 ms 19292 KB Output is correct
11 Correct 349 ms 29508 KB Output is correct
12 Correct 343 ms 29512 KB Output is correct
13 Correct 341 ms 29772 KB Output is correct
14 Correct 345 ms 29508 KB Output is correct
15 Correct 356 ms 29508 KB Output is correct
16 Correct 351 ms 29776 KB Output is correct
17 Correct 360 ms 29904 KB Output is correct
18 Correct 361 ms 29772 KB Output is correct
19 Correct 339 ms 29744 KB Output is correct
20 Correct 344 ms 29708 KB Output is correct
21 Correct 2152 ms 64832 KB Output is correct
22 Correct 2118 ms 63672 KB Output is correct
23 Correct 2146 ms 64896 KB Output is correct
24 Correct 2158 ms 64920 KB Output is correct
25 Correct 2113 ms 64036 KB Output is correct
26 Correct 2096 ms 64952 KB Output is correct
27 Correct 2119 ms 63160 KB Output is correct
28 Correct 2108 ms 64732 KB Output is correct
29 Correct 2201 ms 64184 KB Output is correct
30 Correct 2092 ms 63924 KB Output is correct