oj.uz

Submission #446009

# Submission time Handle Problem Language Result Execution time Memory
446009 2021-07-20T12:44:35 Z grt Index (COCI21_index) C++17
60 / 110
 2500 ms 26244 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) {
		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});
				}
			}
		}
		bool any = false;
		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;
				any = true;
			}
		}
		if(!any) break;
	}
	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 7 ms 5068 KB Output is correct
2 Correct 7 ms 5068 KB Output is correct
3 Correct 6 ms 5068 KB Output is correct
4 Correct 7 ms 5068 KB Output is correct
5 Correct 6 ms 5068 KB Output is correct
6 Correct 6 ms 5068 KB Output is correct
7 Correct 6 ms 5152 KB Output is correct
8 Correct 6 ms 5068 KB Output is correct
9 Correct 7 ms 5068 KB Output is correct
10 Correct 8 ms 5068 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5068 KB Output is correct
2 Correct 7 ms 5068 KB Output is correct
3 Correct 6 ms 5068 KB Output is correct
4 Correct 7 ms 5068 KB Output is correct
5 Correct 6 ms 5068 KB Output is correct
6 Correct 6 ms 5068 KB Output is correct
7 Correct 6 ms 5152 KB Output is correct
8 Correct 6 ms 5068 KB Output is correct
9 Correct 7 ms 5068 KB Output is correct
10 Correct 8 ms 5068 KB Output is correct
11 Correct 653 ms 10708 KB Output is correct
12 Correct 635 ms 10576 KB Output is correct
13 Correct 595 ms 10584 KB Output is correct
14 Correct 615 ms 10564 KB Output is correct
15 Correct 640 ms 10568 KB Output is correct
16 Correct 629 ms 10564 KB Output is correct
17 Correct 607 ms 10692 KB Output is correct
18 Correct 602 ms 10564 KB Output is correct
19 Correct 626 ms 10568 KB Output is correct
20 Correct 646 ms 10640 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5068 KB Output is correct
2 Correct 7 ms 5068 KB Output is correct
3 Correct 6 ms 5068 KB Output is correct
4 Correct 7 ms 5068 KB Output is correct
5 Correct 6 ms 5068 KB Output is correct
6 Correct 6 ms 5068 KB Output is correct
7 Correct 6 ms 5152 KB Output is correct
8 Correct 6 ms 5068 KB Output is correct
9 Correct 7 ms 5068 KB Output is correct
10 Correct 8 ms 5068 KB Output is correct
11 Correct 653 ms 10708 KB Output is correct
12 Correct 635 ms 10576 KB Output is correct
13 Correct 595 ms 10584 KB Output is correct
14 Correct 615 ms 10564 KB Output is correct
15 Correct 640 ms 10568 KB Output is correct
16 Correct 629 ms 10564 KB Output is correct
17 Correct 607 ms 10692 KB Output is correct
18 Correct 602 ms 10564 KB Output is correct
19 Correct 626 ms 10568 KB Output is correct
20 Correct 646 ms 10640 KB Output is correct
21 Execution timed out 2567 ms 26244 KB Time limit exceeded
22 Halted 0 ms 0 KB -