Submission #633970

#	Time	Username	Problem	Language	Result	Execution time	Memory
633970		vovamr	Index (COCI21_index)	C++17	110 / 110	985 ms	57824 KiB

index

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 2e5 + 5; int w = 0;
struct node { int l, r, s; } t[22 * N];
inline int nd(int x) { int v = w++; t[v] = {-1, -1, x}; return v; }
inline int nd(int l, int r) { int v = w++; t[v] = {l, r, t[l].s + t[r].s}; return v; }
inline int build(int vl, int vr) {
	if (vl == vr) return nd(0);
	int m = vl + vr >> 1;
	return nd(build(vl, m), build(m + 1, vr));
}
inline int upd(int v, int vl, int vr, int pos, int x) {
	if (vl == vr) return nd(t[v].s + x);
	int m = vl + vr >> 1;
	if (pos <= m) return nd(upd(t[v].l, vl, m, pos, x), t[v].r);
	else return nd(t[v].l, upd(t[v].r, m + 1, vr, pos, x));
}
inline int get(int v, int vl, int vr, int l, int r) {
	if (vl == l && vr == r) return t[v].s;
	int m = vl + vr >> 1;
	if (r <= m) return get(t[v].l, vl, m, l, r);
	else if (l > m) return get(t[v].r, m + 1, vr, l, r);
	else return get(t[v].l,vl,m,l,m)+get(t[v].r,m+1,vr,m+1,r);
}

int act[N];

inline void solve() {
	int n, q;
	cin >> n >> q;
	ve<int> a(n);
	for (auto &i : a) cin >> i;

	ve<pii> ar(n);
	for (int i = 0; i < n; ++i) ar[i] = {a[i], i};
	sort(all(ar)); reverse(all(ar));

	ve<int> rt(n + 1);
	rt[0] = build(0, n - 1);

	for (int i = 0; i < n; ++i) {
		rt[i + 1] = upd(rt[i], 0, n - 1, ar[i].se, +1);
	}
	for (int i = 0; i < N; ++i) {
		int l = 1, r = n, m, ans = 0;
		while (l <= r) {
			m = l + r >> 1;
			if (ar[m - 1].fi >= i) ans = m, l = m + 1;
			else r = m - 1;
		} act[i] = ans;
	}

	while (q--) {
		int l, r;
		cin >> l >> r, --l, --r;

		int le = 0, re = n, m, ans = 0;
		while (le <= re) {
			m = le + re >> 1;
			int cnt = get(rt[act[m]], 0, n - 1, l, r);
			if (cnt >= m) ans = m, le = m + 1;
			else re = m - 1;
		}
		cout << ans << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message (stderr)

index.cpp: In function 'int build(int, int)':
index.cpp:29:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  int m = vl + vr >> 1;
      |          ~~~^~~~
index.cpp: In function 'int upd(int, int, int, int, int)':
index.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |  int m = vl + vr >> 1;
      |          ~~~^~~~
index.cpp: In function 'int get(int, int, int, int, int)':
index.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  int m = vl + vr >> 1;
      |          ~~~^~~~
index.cpp: In function 'void solve()':
index.cpp:67:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |    m = l + r >> 1;
      |        ~~^~~
index.cpp:79:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |    m = le + re >> 1;
      |        ~~~^~~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50