Submission #851295

#	Time	Username	Problem	Language	Result	Execution time	Memory
851295		dosts	Index (COCI21_index)	C++14	60 / 110	2512 ms	51472 KiB

index

#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
//#define int long long
#define vi vector<int>
#define pb push_back
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
const int N = 2e5+1;
vi a(N);
vector<int> t[4*N];


vi merge(vi& a,vi& b) {
	int ptr = 0;
	int ptr2 = 0;
	int sz1 = a.size();
	int sz2 = b.size();
	vi v;
	while (ptr < sz1 && ptr2 < sz2) {
		if (a[ptr] > b[ptr2]) v.pb(a[ptr++]);
		else v.pb(b[ptr2++]);
	} 
	while (ptr<sz1) {
		v.pb(a[ptr++]);
	}
	while (ptr2<sz2) {
		v.pb(b[ptr2++]);
	}
	return v;
}

void build(int node,int l,int r) {
	if (l == r) {
		t[node].pb(a[l]);
		return;
	}
	int m = (l+r) >> 1;
	build(2*node,l,m);
	build(2*node+1,m+1,r);
	t[node] = merge(t[2*node],t[2*node+1]);
}

int f(vi& v,int x) {
	int l = 0;
	int r = v.size()-1;
	while (l<=r) {
		int m = (l+r) >> 1;
		if (v[m] < x) r = m-1;
		else l = m+1;
	}
	return l;
}

int query(int node,int l,int r,int L,int R,int x) {
	if (l > R || r < L) return 0;
	if (l >= L && r <= R) return f(t[node],x);
	int m = (l+r) >> 1;
	return query(2*node,l,m,L,R,x)+query(2*node+1,m+1,r,L,R,x);
}




void solve() {
	int n,q;
	cin >> n >> q;
	for (int i=1;i<=n;i++) cin >> a[i];
	build(1,1,n);
	while (q--) {
		int l,r;
		cin >> l >> r;
		int L=1;
		int R=n;
		while (L<=R) {
			int x = (L+R) >> 1;
			int y = query(1,1,n,l,r,x);
			//icout << x sp y << endl;
			if (y >= x) L = x+1;
			else R = x-1;
		}
		cout << R << endl;
	}
}    
 
 
 
                                
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}
 
 
 

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50