oj.uz

Submission #851295

# Submission time Handle Problem Language Result Execution time Memory
851295 2023-09-19T12:17:13 Z dosts Index (COCI21_index) C++14
60 / 110
 2500 ms 51472 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20056 KB Output is correct
2 Correct 8 ms 20056 KB Output is correct
3 Correct 8 ms 20056 KB Output is correct
4 Correct 8 ms 20060 KB Output is correct
5 Correct 9 ms 20056 KB Output is correct
6 Correct 8 ms 20056 KB Output is correct
7 Correct 8 ms 20056 KB Output is correct
8 Correct 8 ms 20060 KB Output is correct
9 Correct 8 ms 20056 KB Output is correct
10 Correct 9 ms 20056 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20056 KB Output is correct
2 Correct 8 ms 20056 KB Output is correct
3 Correct 8 ms 20056 KB Output is correct
4 Correct 8 ms 20060 KB Output is correct
5 Correct 9 ms 20056 KB Output is correct
6 Correct 8 ms 20056 KB Output is correct
7 Correct 8 ms 20056 KB Output is correct
8 Correct 8 ms 20060 KB Output is correct
9 Correct 8 ms 20056 KB Output is correct
10 Correct 9 ms 20056 KB Output is correct
11 Correct 547 ms 27712 KB Output is correct
12 Correct 565 ms 27860 KB Output is correct
13 Correct 581 ms 27884 KB Output is correct
14 Correct 565 ms 27716 KB Output is correct
15 Correct 549 ms 27448 KB Output is correct
16 Correct 541 ms 27340 KB Output is correct
17 Correct 550 ms 27340 KB Output is correct
18 Correct 540 ms 27368 KB Output is correct
19 Correct 554 ms 27404 KB Output is correct
20 Correct 540 ms 27672 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20056 KB Output is correct
2 Correct 8 ms 20056 KB Output is correct
3 Correct 8 ms 20056 KB Output is correct
4 Correct 8 ms 20060 KB Output is correct
5 Correct 9 ms 20056 KB Output is correct
6 Correct 8 ms 20056 KB Output is correct
7 Correct 8 ms 20056 KB Output is correct
8 Correct 8 ms 20060 KB Output is correct
9 Correct 8 ms 20056 KB Output is correct
10 Correct 9 ms 20056 KB Output is correct
11 Correct 547 ms 27712 KB Output is correct
12 Correct 565 ms 27860 KB Output is correct
13 Correct 581 ms 27884 KB Output is correct
14 Correct 565 ms 27716 KB Output is correct
15 Correct 549 ms 27448 KB Output is correct
16 Correct 541 ms 27340 KB Output is correct
17 Correct 550 ms 27340 KB Output is correct
18 Correct 540 ms 27368 KB Output is correct
19 Correct 554 ms 27404 KB Output is correct
20 Correct 540 ms 27672 KB Output is correct
21 Execution timed out 2512 ms 51472 KB Time limit exceeded
22 Halted 0 ms 0 KB -