oj.uz

Submission #923661

# Submission time Handle Problem Language Result Execution time Memory
923661 2024-02-07T14:34:52 Z Isam Index (COCI21_index) C++17
110 / 110
 961 ms 6172 KB 
#include<bits/stdc++.h>

#define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file freopen("condense2.in", "r", stdin), freopen("condense2.out", "w", stdout);
#define eb emplace_back
#define all(x) x.begin(), x.end()

using namespace std;

const int sz = 200005;

int n, Q, c[sz], tree[sz], ans[sz];

struct query{
	int l, r, index;
} q[sz];

bool cmp(query &a, query &b){
	if(a.l/316 != b.l/316) return a.l/316 < b.l/316;
	return a.r/316 < b.r/316;
}


/*
1 1000

300 500

1) 1000 + 800 = 1800


2) 500 + 800 = 1300

*/

inline void update(int pos, int val){
	while(pos <= n){
		tree[pos] += val;
		pos += (pos & (-pos));
	}
	return;
}

int get(int l, int r){
	if(l ^ 1) return get(1, r) - get(1, l - 1);
	int res(0);
	while(r > 0){
		res += tree[r];
		r -= (r & (-r));
	}
	return res;
}

inline void add(int x){
	update(x, 1);
	return;
}

inline void del(int x){
	update(x, -1);
	return;
}

int main(){
	speed;
	cin >> n >> Q;
	for(register int i = 1; i <= n; ++i){
		cin >> c[i];
	}
	for(register int i = 1; i <= Q; ++i){
		cin >> q[i].l >> q[i].r, q[i].index = i;
	}
	sort(q+1,q+Q+1,cmp);
	int l(1), r(0);
	for(register int i = 1; i <= Q; ++i){
		while(r < q[i].r) add(c[++r]);
		while(r > q[i].r) del(c[r--]);
		while(l < q[i].l) del(c[l++]);
		while(l > q[i].l) add(c[--l]);
		int L(1), R{r - l + 1}, mid, best;
		while(L <= R){
			mid = L + ((R - L) >> 1);
			if(get(mid, n) >= mid){
				best = mid, L = mid + 1;
			}else{
				R = mid - 1;
			}
		}
		ans[q[i].index] = best;
	}
	for(register int i = 1; i <= Q; ++i){
		cout << ans[i] << '\n';
	}
	return 0;
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:67:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   67 |  for(register int i = 1; i <= n; ++i){
      |                   ^
index.cpp:70:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   70 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:75:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   75 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:91:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   91 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:89:19: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |   ans[q[i].index] = best;
      |   ~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 135 ms 4988 KB Output is correct
12 Correct 133 ms 4944 KB Output is correct
13 Correct 134 ms 4948 KB Output is correct
14 Correct 138 ms 4944 KB Output is correct
15 Correct 134 ms 4976 KB Output is correct
16 Correct 135 ms 4984 KB Output is correct
17 Correct 137 ms 4976 KB Output is correct
18 Correct 139 ms 4976 KB Output is correct
19 Correct 136 ms 4968 KB Output is correct
20 Correct 144 ms 4972 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 135 ms 4988 KB Output is correct
12 Correct 133 ms 4944 KB Output is correct
13 Correct 134 ms 4948 KB Output is correct
14 Correct 138 ms 4944 KB Output is correct
15 Correct 134 ms 4976 KB Output is correct
16 Correct 135 ms 4984 KB Output is correct
17 Correct 137 ms 4976 KB Output is correct
18 Correct 139 ms 4976 KB Output is correct
19 Correct 136 ms 4968 KB Output is correct
20 Correct 144 ms 4972 KB Output is correct
21 Correct 895 ms 6156 KB Output is correct
22 Correct 902 ms 6164 KB Output is correct
23 Correct 904 ms 6160 KB Output is correct
24 Correct 900 ms 6156 KB Output is correct
25 Correct 871 ms 6172 KB Output is correct
26 Correct 961 ms 6156 KB Output is correct
27 Correct 932 ms 6156 KB Output is correct
28 Correct 949 ms 6156 KB Output is correct
29 Correct 936 ms 6156 KB Output is correct
30 Correct 914 ms 6156 KB Output is correct