oj.uz

Submission #715123

# Submission time Handle Problem Language Result Execution time Memory
715123 2023-03-25T23:31:50 Z TheConverseEngineer Index (COCI21_index) C++17
60 / 110
 2500 ms 38264 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define sqr(x) ((ll)(x))*(x)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct MergeSortTree {
	vector<vi> s;
	void buildFullTree() {
		for (int i = sz(s)/2-1; i > 0; i--) { 
			s[i].resize(sz(s[i<<1]) + sz(s[i<<1|1]));
			merge(all(s[i<<1]), all(s[i<<1|1]), s[i].begin());
		}
	}
	int countGreater(int l, int r, int k) { 
		int output = 0;
		for (l += sz(s)/2, r += sz(s)/2; l < r; l /= 2, r /= 2) {
			if (l&1) output += s[l].end() - upper_bound(all(s[l]), k), l++;
			if (r&1) --r, output += s[r].end() - upper_bound(all(s[r]), k);
		}
		return output;
	}
};

int N, Q;
MergeSortTree tree;


int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> Q; tree.s.resize(2*N, vi(0));
	FOR(i, 0, N) {
		int a; cin >> a; tree.s[N+i] = {a};
	}
	tree.buildFullTree();

	FOR(query, 0, Q) {
		int l, r; cin >> l >> r;
		int works = -1;
		for (int move = 262144; move > 0; move /= 2) {
			if (tree.countGreater(l-1, r, works+move-1) >= works+move) works += move;
		}
		cout << works << "\n";
	}
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 7 ms 468 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 6 ms 464 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 5 ms 468 KB Output is correct
11 Correct 539 ms 9320 KB Output is correct
12 Correct 558 ms 9312 KB Output is correct
13 Correct 550 ms 9364 KB Output is correct
14 Correct 567 ms 9408 KB Output is correct
15 Correct 582 ms 9280 KB Output is correct
16 Correct 574 ms 9296 KB Output is correct
17 Correct 548 ms 9376 KB Output is correct
18 Correct 579 ms 9316 KB Output is correct
19 Correct 602 ms 9388 KB Output is correct
20 Correct 560 ms 9548 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 7 ms 468 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 6 ms 464 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 5 ms 468 KB Output is correct
11 Correct 539 ms 9320 KB Output is correct
12 Correct 558 ms 9312 KB Output is correct
13 Correct 550 ms 9364 KB Output is correct
14 Correct 567 ms 9408 KB Output is correct
15 Correct 582 ms 9280 KB Output is correct
16 Correct 574 ms 9296 KB Output is correct
17 Correct 548 ms 9376 KB Output is correct
18 Correct 579 ms 9316 KB Output is correct
19 Correct 602 ms 9388 KB Output is correct
20 Correct 560 ms 9548 KB Output is correct
21 Execution timed out 2574 ms 38264 KB Time limit exceeded
22 Halted 0 ms 0 KB -