oj.uz

Submission #403852

# Submission time Handle Problem Language Result Execution time Memory
403852 2021-05-13T14:16:05 Z silverfish Index (COCI21_index) C++17
60 / 110
 2500 ms 134120 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

/*<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;
}

Compilation message

index.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
index.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      |

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 381 ms 30576 KB Output is correct
12 Correct 380 ms 30640 KB Output is correct
13 Correct 384 ms 30568 KB Output is correct
14 Correct 395 ms 30604 KB Output is correct
15 Correct 396 ms 30636 KB Output is correct
16 Correct 383 ms 30556 KB Output is correct
17 Correct 394 ms 30612 KB Output is correct
18 Correct 387 ms 30576 KB Output is correct
19 Correct 381 ms 30736 KB Output is correct
20 Correct 389 ms 30756 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 381 ms 30576 KB Output is correct
12 Correct 380 ms 30640 KB Output is correct
13 Correct 384 ms 30568 KB Output is correct
14 Correct 395 ms 30604 KB Output is correct
15 Correct 396 ms 30636 KB Output is correct
16 Correct 383 ms 30556 KB Output is correct
17 Correct 394 ms 30612 KB Output is correct
18 Correct 387 ms 30576 KB Output is correct
19 Correct 381 ms 30736 KB Output is correct
20 Correct 389 ms 30756 KB Output is correct
21 Correct 2446 ms 134120 KB Output is correct
22 Execution timed out 2590 ms 134112 KB Time limit exceeded
23 Halted 0 ms 0 KB -