oj.uz

Submission #446011

# Submission time Handle Problem Language Result Execution time Memory
446011 2021-07-20T12:52:30 Z grt Index (COCI21_index) C++17
110 / 110
 697 ms 19472 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,mx;
int val[nax], l[nax], r[nax], mid[nax], ans[nax];
pi prz[nax];
vi contain[nax];

int T[nax];

void add(int a, int x) {
	while(a > 0) {
		T[a] += x;
		a -= (a & (-a));
	}
}

int ask(int a) {
	int w = 0;
	while(a < mx) {
		w += T[a];
		a += (a & (-a));
	}
	return w;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		cin >> val[i];
		mx = max(mx, 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) {
		for(int i = 0; i <= n; ++i) {
			if(i > 0) {
				add(val[i], 1);
			}
			for(auto x : contain[i]) {
				if(x < 0) {
					ans[-x] = -ask(mid[-x]);
				} else {
					ans[x] += ask(mid[x]);
				}
			}
		}
		for(int i = 1; i <= n; ++i) {
			add(val[i], -1);
		}
		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 4 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 119 ms 7708 KB Output is correct
12 Correct 118 ms 7704 KB Output is correct
13 Correct 111 ms 7696 KB Output is correct
14 Correct 116 ms 7688 KB Output is correct
15 Correct 114 ms 7700 KB Output is correct
16 Correct 131 ms 7816 KB Output is correct
17 Correct 115 ms 7748 KB Output is correct
18 Correct 114 ms 7748 KB Output is correct
19 Correct 140 ms 7620 KB Output is correct
20 Correct 113 ms 7688 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 119 ms 7708 KB Output is correct
12 Correct 118 ms 7704 KB Output is correct
13 Correct 111 ms 7696 KB Output is correct
14 Correct 116 ms 7688 KB Output is correct
15 Correct 114 ms 7700 KB Output is correct
16 Correct 131 ms 7816 KB Output is correct
17 Correct 115 ms 7748 KB Output is correct
18 Correct 114 ms 7748 KB Output is correct
19 Correct 140 ms 7620 KB Output is correct
20 Correct 113 ms 7688 KB Output is correct
21 Correct 648 ms 15664 KB Output is correct
22 Correct 675 ms 19348 KB Output is correct
23 Correct 639 ms 19380 KB Output is correct
24 Correct 646 ms 19472 KB Output is correct
25 Correct 657 ms 19404 KB Output is correct
26 Correct 697 ms 19464 KB Output is correct
27 Correct 657 ms 19396 KB Output is correct
28 Correct 624 ms 19368 KB Output is correct
29 Correct 641 ms 19364 KB Output is correct
30 Correct 659 ms 19364 KB Output is correct