oj.uz

답안 #403861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403861 2021-05-13T14:21:03 Z silverfish Index (COCI21_index) C++14
60 / 110
 2500 ms 134376 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 = 18; 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

# 결과 실행 시간 메모리 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 5 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

# 결과 실행 시간 메모리 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 5 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 395 ms 30648 KB Output is correct
12 Correct 401 ms 30584 KB Output is correct
13 Correct 387 ms 30776 KB Output is correct
14 Correct 388 ms 30620 KB Output is correct
15 Correct 392 ms 30652 KB Output is correct
16 Correct 402 ms 30660 KB Output is correct
17 Correct 391 ms 30532 KB Output is correct
18 Correct 404 ms 30652 KB Output is correct
19 Correct 398 ms 30760 KB Output is correct
20 Correct 385 ms 30584 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 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 5 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 395 ms 30648 KB Output is correct
12 Correct 401 ms 30584 KB Output is correct
13 Correct 387 ms 30776 KB Output is correct
14 Correct 388 ms 30620 KB Output is correct
15 Correct 392 ms 30652 KB Output is correct
16 Correct 402 ms 30660 KB Output is correct
17 Correct 391 ms 30532 KB Output is correct
18 Correct 404 ms 30652 KB Output is correct
19 Correct 398 ms 30760 KB Output is correct
20 Correct 385 ms 30584 KB Output is correct
21 Execution timed out 2590 ms 134376 KB Time limit exceeded
22 Halted 0 ms 0 KB -