oj.uz

Submission #403847

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

/*<DEBUG>*/
#define tem template <typename 
#define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i)
#define _op debug& operator<<
tem C > auto test(C *x) -> decltype(cerr << *x, 0LL);
tem C > char test(...);
tem C > struct itr{C begin, end; };
tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; }
struct debug{
#ifdef _LOCAL
	~debug(){ cerr << endl; }
	tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; }
	tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); }
	tem T, typename U > _op (pair<T, U> i){ 
		return *this << "< " << i.first << " , " << i.second << " >"; }
	tem T> _op (itr<T> i){
		*this <<  "{ ";
		for(auto it = i.begin; it != i.end; it++){
			*this << " , " + (it==i.begin?2:0) << *it;
		}
		return *this << " }";
	}
#else
tem T> _op (const T&) { return *this; }
#endif 
};

string _ARR_(int* arr, int sz){
	string ret = "{ " + to_string(arr[0]); 
	for(int i = 1; i < sz; i++) ret += " , " +  to_string(arr[i]);
	ret += " }"; return ret;
}

#define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]"
/*</DEBUG>*/

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#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 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 4 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 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 375 ms 30660 KB Output is correct
12 Correct 408 ms 30672 KB Output is correct
13 Correct 379 ms 30820 KB Output is correct
14 Correct 478 ms 30800 KB Output is correct
15 Correct 389 ms 30768 KB Output is correct
16 Correct 417 ms 30740 KB Output is correct
17 Correct 461 ms 30780 KB Output is correct
18 Correct 416 ms 30776 KB Output is correct
19 Correct 379 ms 30788 KB Output is correct
20 Correct 399 ms 30860 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 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 375 ms 30660 KB Output is correct
12 Correct 408 ms 30672 KB Output is correct
13 Correct 379 ms 30820 KB Output is correct
14 Correct 478 ms 30800 KB Output is correct
15 Correct 389 ms 30768 KB Output is correct
16 Correct 417 ms 30740 KB Output is correct
17 Correct 461 ms 30780 KB Output is correct
18 Correct 416 ms 30776 KB Output is correct
19 Correct 379 ms 30788 KB Output is correct
20 Correct 399 ms 30860 KB Output is correct
21 Correct 2387 ms 134540 KB Output is correct
22 Execution timed out 2558 ms 137804 KB Time limit exceeded
23 Halted 0 ms 0 KB -