oj.uz

Submission #446007

# Submission time Handle Problem Language Result Execution time Memory
446007 2021-07-20T12:42:50 Z grt Index (COCI21_index) C++17
60 / 110
 2500 ms 29820 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

typedef tree<pi,null_type,less<pi>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

const int nax = 200 * 1000 + 10, INF = 1e9;
int n, q;
int val[nax], l[nax], r[nax], mid[nax], ans[nax];
pi prz[nax];
vi contain[nax];
ordered_set S;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		cin >> val[i];
	}
	for(int i = 1; i <= q; ++i) {
		cin >> prz[i].ST >> prz[i].ND;
		l[i] = 1; r[i] = prz[i].ND - prz[i].ST + 1;
		mid[i] = (l[i] + r[i]) / 2;
		contain[prz[i].ST - 1].PB(-i);
		contain[prz[i].ND].PB(i);
	}
	for(int rep = 0; rep < 20; ++rep) {
		S.clear();
		int id = 1;
		for(int i = 0; i <= n; ++i) {
			if(i > 0) {
				S.insert({-val[i], id++});
			}
			for(auto x : contain[i]) {
				if(x < 0) {
					ans[-x] = -S.order_of_key({-mid[-x], INF});
				} else {
					ans[x] += S.order_of_key({-mid[x], INF});
				}
			}
		}
		for(int i = 1; i <= q; ++i) {
			if(l[i] <= r[i]) {
				if(ans[i] >= mid[i]) {
					l[i] = mid[i] + 1;
				} else {
					r[i] = mid[i] - 1;
				}
				mid[i] = (l[i] + r[i]) / 2;
			}
		}
	}
	for(int i = 1; i <= q; ++i) {
		cout << l[i] - 1 << "\n";
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5196 KB Output is correct
2 Correct 10 ms 5168 KB Output is correct
3 Correct 9 ms 5068 KB Output is correct
4 Correct 10 ms 5068 KB Output is correct
5 Correct 12 ms 5068 KB Output is correct
6 Correct 10 ms 5168 KB Output is correct
7 Correct 11 ms 5164 KB Output is correct
8 Correct 10 ms 5068 KB Output is correct
9 Correct 9 ms 5068 KB Output is correct
10 Correct 9 ms 5164 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5196 KB Output is correct
2 Correct 10 ms 5168 KB Output is correct
3 Correct 9 ms 5068 KB Output is correct
4 Correct 10 ms 5068 KB Output is correct
5 Correct 12 ms 5068 KB Output is correct
6 Correct 10 ms 5168 KB Output is correct
7 Correct 11 ms 5164 KB Output is correct
8 Correct 10 ms 5068 KB Output is correct
9 Correct 9 ms 5068 KB Output is correct
10 Correct 9 ms 5164 KB Output is correct
11 Correct 747 ms 11400 KB Output is correct
12 Correct 689 ms 11388 KB Output is correct
13 Correct 739 ms 11388 KB Output is correct
14 Correct 686 ms 11308 KB Output is correct
15 Correct 711 ms 11636 KB Output is correct
16 Correct 751 ms 11384 KB Output is correct
17 Correct 696 ms 11460 KB Output is correct
18 Correct 701 ms 11384 KB Output is correct
19 Correct 735 ms 11384 KB Output is correct
20 Correct 713 ms 11380 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5196 KB Output is correct
2 Correct 10 ms 5168 KB Output is correct
3 Correct 9 ms 5068 KB Output is correct
4 Correct 10 ms 5068 KB Output is correct
5 Correct 12 ms 5068 KB Output is correct
6 Correct 10 ms 5168 KB Output is correct
7 Correct 11 ms 5164 KB Output is correct
8 Correct 10 ms 5068 KB Output is correct
9 Correct 9 ms 5068 KB Output is correct
10 Correct 9 ms 5164 KB Output is correct
11 Correct 747 ms 11400 KB Output is correct
12 Correct 689 ms 11388 KB Output is correct
13 Correct 739 ms 11388 KB Output is correct
14 Correct 686 ms 11308 KB Output is correct
15 Correct 711 ms 11636 KB Output is correct
16 Correct 751 ms 11384 KB Output is correct
17 Correct 696 ms 11460 KB Output is correct
18 Correct 701 ms 11384 KB Output is correct
19 Correct 735 ms 11384 KB Output is correct
20 Correct 713 ms 11380 KB Output is correct
21 Execution timed out 2552 ms 29820 KB Time limit exceeded
22 Halted 0 ms 0 KB -