oj.uz

Submission #759514

# Submission time Handle Problem Language Result Execution time Memory
759514 2023-06-16T11:05:14 Z dsyz Index (COCI21_index) C++17
110 / 110
 1390 ms 201948 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MAXN (200005)
struct node {
	ll s,e,m,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) >> 1;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	node(node *u){
		s = u->s, e = u->e, m = u->m;
		v = u->v;
		l = u->l, r = u->r;
	}
	void update(ll x,ll val){
		if(s == e){
			v += val;
			return;
		}else{
			if(x > m){
				r = new node(r);
				r -> update(x,val);
			}else{
				l = new node(l);
				l -> update(x,val);
			}
			v = l->v + r->v;
		}
	}
	ll query(ll x,ll y){
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r -> query(x,y);
			else if(y <= m) return l -> query(x,y);
			else return l -> query(x,m) + r -> query(m + 1,y);
		}
	}
} *root[MAXN];
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,Q;
	cin>>N>>Q;
	ll arr[N];
	deque<pair<ll,ll> > p;
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
		p.push_back({arr[i],i});
	}
	sort(p.begin(),p.end(),greater<pair<ll,ll> >());
	root[MAXN - 1] = new node(0,N - 1);
	for(ll i = MAXN - 2;i >= 0;i--){
		root[i] = new node(root[i + 1]);
		while(!p.empty() && p.front().first >= i){
			ll val = p.front().first;
			ll ind = p.front().second;
			root[i] -> update(ind,1);
			p.pop_front();
		}
	}
	for(ll q = 0;q < Q;q++){
		ll l,r;
		cin>>l>>r;
		l--;
		r--;
		ll high = MAXN;
		ll low = 0;
		while(high - low > 1){
			ll mid = (high + low) / 2;
			if(root[mid] -> query(l,r) >= mid){
				low = mid;
			}else{
				high = mid;
			}
		}
		cout<<low<<'\n';
	}
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:63:7: warning: unused variable 'val' [-Wunused-variable]
   63 |    ll val = p.front().first;
      |       ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11860 KB Output is correct
2 Correct 9 ms 11860 KB Output is correct
3 Correct 10 ms 11860 KB Output is correct
4 Correct 9 ms 11812 KB Output is correct
5 Correct 9 ms 11860 KB Output is correct
6 Correct 9 ms 11852 KB Output is correct
7 Correct 9 ms 11856 KB Output is correct
8 Correct 9 ms 11860 KB Output is correct
9 Correct 9 ms 11860 KB Output is correct
10 Correct 9 ms 11784 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11860 KB Output is correct
2 Correct 9 ms 11860 KB Output is correct
3 Correct 10 ms 11860 KB Output is correct
4 Correct 9 ms 11812 KB Output is correct
5 Correct 9 ms 11860 KB Output is correct
6 Correct 9 ms 11852 KB Output is correct
7 Correct 9 ms 11856 KB Output is correct
8 Correct 9 ms 11860 KB Output is correct
9 Correct 9 ms 11860 KB Output is correct
10 Correct 9 ms 11784 KB Output is correct
11 Correct 237 ms 54096 KB Output is correct
12 Correct 221 ms 54076 KB Output is correct
13 Correct 220 ms 54060 KB Output is correct
14 Correct 245 ms 54076 KB Output is correct
15 Correct 232 ms 54152 KB Output is correct
16 Correct 237 ms 54128 KB Output is correct
17 Correct 223 ms 54092 KB Output is correct
18 Correct 227 ms 54212 KB Output is correct
19 Correct 223 ms 54024 KB Output is correct
20 Correct 223 ms 54088 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11860 KB Output is correct
2 Correct 9 ms 11860 KB Output is correct
3 Correct 10 ms 11860 KB Output is correct
4 Correct 9 ms 11812 KB Output is correct
5 Correct 9 ms 11860 KB Output is correct
6 Correct 9 ms 11852 KB Output is correct
7 Correct 9 ms 11856 KB Output is correct
8 Correct 9 ms 11860 KB Output is correct
9 Correct 9 ms 11860 KB Output is correct
10 Correct 9 ms 11784 KB Output is correct
11 Correct 237 ms 54096 KB Output is correct
12 Correct 221 ms 54076 KB Output is correct
13 Correct 220 ms 54060 KB Output is correct
14 Correct 245 ms 54076 KB Output is correct
15 Correct 232 ms 54152 KB Output is correct
16 Correct 237 ms 54128 KB Output is correct
17 Correct 223 ms 54092 KB Output is correct
18 Correct 227 ms 54212 KB Output is correct
19 Correct 223 ms 54024 KB Output is correct
20 Correct 223 ms 54088 KB Output is correct
21 Correct 1342 ms 201872 KB Output is correct
22 Correct 1349 ms 201820 KB Output is correct
23 Correct 1341 ms 201856 KB Output is correct
24 Correct 1390 ms 201908 KB Output is correct
25 Correct 1325 ms 201948 KB Output is correct
26 Correct 1379 ms 201932 KB Output is correct
27 Correct 1317 ms 201876 KB Output is correct
28 Correct 1305 ms 201884 KB Output is correct
29 Correct 1333 ms 201896 KB Output is correct
30 Correct 1353 ms 201924 KB Output is correct