oj.uz

Submission #403842

# Submission time Handle Problem Language Result Execution time Memory
403842 2021-05-13T14:11:05 Z silverfish Index (COCI21_index) C++14
60 / 110
 2500 ms 137416 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

#define pb push_back
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define TC int __TC__; cin >> __TC__; while(__TC__--)
#define ar array

const int INF = 1e9 + 7, N = 2e5;

int n, q;

struct node{
	node* left = nullptr,* right = nullptr;
	int v = 0;
};

node* root[N+1];

void build(node *rt, int lx, int rx){
	if(lx == rx) return;
	int m = lx+(rx-lx) / 2;

	rt->left = new node;
	rt->right = new node;
	build(rt->left, lx, m);
	build(rt->right, m+1, rx);
	return;
}

void add(int pos, node* lr, node* nr, int lx, int rx){
	if(lx == rx){
		nr->v=1;
		return;
	}

	int m = lx + (rx - lx) / 2;

	if(pos <= m){ // go left
		nr->right = lr->right;
		nr->left = new node;
		add(pos, lr->left, nr->left, lx, m);
	}else{ // go right
		nr->left = lr->left;
		nr->right = new node;
		add(pos, lr->right, nr->right, m+1, rx);
	}
	nr->v = nr->left->v + nr->right->v;
}

int get(int l, int r, node* rt, int lx, int rx){
	if(r < lx || l > rx) return 0;
	if(lx >= l && rx <= r) return rt->v;
	int m = lx + (rx - lx) / 2;

	return get(l, r, rt->left, lx, m) + get(l, r, rt->right, m+1, rx);
}

int main(void)
{
	FAST;
	cin >> n >> q;
	vector<ar<int,2>> a(n);
	for(int i = 0; i < n; ++i){
		cin >> a[i][0];
		a[i][1] = i+1;
	}

	sort(a.rbegin(), a.rend());


	root[0] = new node;
	build(root[0], 1, n);
	for(int i = 1; i <= n; ++i){
		root[i] = new node;	
		add(a[i-1][1], root[i-1], root[i], 1, n); 
	}
	
	sort(a.begin(), a.end());
	while(q--){
		int l, r; cin >> l >> r;
		int ans = 1;
		for(int j = 22; j >= 0; --j){
			int nans = ans + (1<<j);
			auto it = lower_bound(a.begin(), a.end(), ar<int,2>{nans, 0});
			if(it == a.end()) continue;
			int pos = n-(it - a.begin());
			if(get(l, r, root[pos], 1, n) >= nans) ans += (1<<j);
		}
		cout << ans << '\n';
	}

	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 716 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 4 ms 716 KB Output is correct
5 Correct 4 ms 660 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 6 ms 760 KB Output is correct
10 Correct 5 ms 716 KB Output is correct
11 Correct 399 ms 31388 KB Output is correct
12 Correct 402 ms 31464 KB Output is correct
13 Correct 403 ms 31552 KB Output is correct
14 Correct 382 ms 31376 KB Output is correct
15 Correct 398 ms 31444 KB Output is correct
16 Correct 417 ms 31520 KB Output is correct
17 Correct 428 ms 31584 KB Output is correct
18 Correct 457 ms 31388 KB Output is correct
19 Correct 547 ms 31428 KB Output is correct
20 Correct 435 ms 31408 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 716 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 4 ms 716 KB Output is correct
5 Correct 4 ms 660 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 6 ms 760 KB Output is correct
10 Correct 5 ms 716 KB Output is correct
11 Correct 399 ms 31388 KB Output is correct
12 Correct 402 ms 31464 KB Output is correct
13 Correct 403 ms 31552 KB Output is correct
14 Correct 382 ms 31376 KB Output is correct
15 Correct 398 ms 31444 KB Output is correct
16 Correct 417 ms 31520 KB Output is correct
17 Correct 428 ms 31584 KB Output is correct
18 Correct 457 ms 31388 KB Output is correct
19 Correct 547 ms 31428 KB Output is correct
20 Correct 435 ms 31408 KB Output is correct
21 Execution timed out 2565 ms 137416 KB Time limit exceeded
22 Halted 0 ms 0 KB -