oj.uz

Submission #845706

# Submission time Handle Problem Language Result Execution time Memory
845706 2023-09-06T15:00:49 Z fanwen Index (COCI21_index) C++17
110 / 110
 1046 ms 245840 KB 
#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

template <class T>
struct Persistent {
	struct node {
		T val;
		int l, r;
		node (T val = 0, int l = 0, int r = 0) : val(val), l(l), r(r) {}
	};
	vector <node> it;
	vector <int> stt;
	int n, version;

private : 
	void update(int idx, int l, int r, int u, T val) {
		if(l > u || r < u) return;
		int cnt = ++version;
		stt[idx] = cnt;
		if(l == r) {
			it[cnt].val = val;
			return;
		}
		int mid = l + r >> 1;
		update(idx << 1, l, mid, u, val);
		update(idx << 1 | 1, mid + 1, r, u, val);
		it[cnt] = node(it[stt[idx << 1]].val + it[stt[idx << 1 | 1]].val, stt[idx << 1], stt[idx << 1 | 1]);
	}

	T get(int idx, int l, int r, int u, int v) {
		if(l > v || r < u) return 0;
		if(l >= u && r <= v) return it[idx].val;
		int mid = l + r >> 1;
		return get(it[idx].l, l, mid, u, v) + get(it[idx].r, mid + 1, r, u, v);
	}
public :
	
	Persistent(int n = 0) : n(n) {
		version = 0;
		resize(n);
	}

	void resize(int n) {
		it.resize(100 * n + 1);
		stt.resize(n << 2 | 1);
	}

	int update(int u, T val) {
		update(1, 1, n, u, val);
		return stt[1];
	}

	T get(int id, int l, int r) {
		return get(id, 1, n, l, r);
	}

	int size() {
		return n;
	}
};


const int MAXN = 2e5 + 5;

int N, Q, root[MAXN];
pair <int, int> a[MAXN];

void you_make_it(void) {
    cin >> N >> Q;
    FOR(i, 1, N) cin >> a[i].first, a[i].second = i;
    sort(a + 1, a + N + 1);
    Persistent <int> per(N);
    FORD(i, N, 1) {
    	root[i] = per.update(a[i].second, 1);
    }
    while(Q--) {
    	int l, r; cin >> l >> r;
    	int L = 0, R = N;
    	while(R - L > 1) {
    		int mid = L + R >> 1;
    		int id = lower_bound(a + 1, a + N + 1, make_pair(mid, 0)) - a;
    		if(per.get(root[id], l, r) >= mid) L = mid;
    		else R = mid;
    		// cout << debug(root[mid]) << " " << mid << '\n';
    	}
    	cout << L << '\n';
    }
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

index.cpp: In function 'void you_make_it()':
index.cpp:94:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |       int mid = L + R >> 1;
      |                 ~~^~~
index.cpp: In instantiation of 'void Persistent<T>::update(int, int, int, int, T) [with T = int]':
index.cpp:63:9:   required from 'int Persistent<T>::update(int, T) [with T = int]'
index.cpp:88:41:   required from here
index.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~
index.cpp: In instantiation of 'T Persistent<T>::get(int, int, int, int, int) [with T = int]':
index.cpp:68:13:   required from 'T Persistent<T>::get(int, int, int) [with T = int]'
index.cpp:96:32:   required from here
index.cpp:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3676 KB Output is correct
2 Correct 2 ms 3536 KB Output is correct
3 Correct 3 ms 3676 KB Output is correct
4 Correct 3 ms 3740 KB Output is correct
5 Correct 3 ms 3676 KB Output is correct
6 Correct 3 ms 3676 KB Output is correct
7 Correct 3 ms 3676 KB Output is correct
8 Correct 3 ms 3676 KB Output is correct
9 Correct 3 ms 3676 KB Output is correct
10 Correct 3 ms 3676 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3676 KB Output is correct
2 Correct 2 ms 3536 KB Output is correct
3 Correct 3 ms 3676 KB Output is correct
4 Correct 3 ms 3740 KB Output is correct
5 Correct 3 ms 3676 KB Output is correct
6 Correct 3 ms 3676 KB Output is correct
7 Correct 3 ms 3676 KB Output is correct
8 Correct 3 ms 3676 KB Output is correct
9 Correct 3 ms 3676 KB Output is correct
10 Correct 3 ms 3676 KB Output is correct
11 Correct 188 ms 63288 KB Output is correct
12 Correct 189 ms 63252 KB Output is correct
13 Correct 183 ms 63060 KB Output is correct
14 Correct 190 ms 63232 KB Output is correct
15 Correct 196 ms 63120 KB Output is correct
16 Correct 184 ms 63052 KB Output is correct
17 Correct 189 ms 63212 KB Output is correct
18 Correct 187 ms 63056 KB Output is correct
19 Correct 184 ms 63060 KB Output is correct
20 Correct 187 ms 63192 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3676 KB Output is correct
2 Correct 2 ms 3536 KB Output is correct
3 Correct 3 ms 3676 KB Output is correct
4 Correct 3 ms 3740 KB Output is correct
5 Correct 3 ms 3676 KB Output is correct
6 Correct 3 ms 3676 KB Output is correct
7 Correct 3 ms 3676 KB Output is correct
8 Correct 3 ms 3676 KB Output is correct
9 Correct 3 ms 3676 KB Output is correct
10 Correct 3 ms 3676 KB Output is correct
11 Correct 188 ms 63288 KB Output is correct
12 Correct 189 ms 63252 KB Output is correct
13 Correct 183 ms 63060 KB Output is correct
14 Correct 190 ms 63232 KB Output is correct
15 Correct 196 ms 63120 KB Output is correct
16 Correct 184 ms 63052 KB Output is correct
17 Correct 189 ms 63212 KB Output is correct
18 Correct 187 ms 63056 KB Output is correct
19 Correct 184 ms 63060 KB Output is correct
20 Correct 187 ms 63192 KB Output is correct
21 Correct 952 ms 245448 KB Output is correct
22 Correct 979 ms 245436 KB Output is correct
23 Correct 971 ms 245712 KB Output is correct
24 Correct 968 ms 245440 KB Output is correct
25 Correct 941 ms 245480 KB Output is correct
26 Correct 1046 ms 245648 KB Output is correct
27 Correct 952 ms 245492 KB Output is correct
28 Correct 959 ms 245716 KB Output is correct
29 Correct 967 ms 245484 KB Output is correct
30 Correct 1000 ms 245840 KB Output is correct