oj.uz

Submission #923658

# Submission time Handle Problem Language Result Execution time Memory
923658 2024-02-07T14:30:20 Z Isam Index (COCI21_index) C++17
110 / 110
 1151 ms 10068 KB 
#include<bits/stdc++.h>

#define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#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/450 != b.l/450) return a.l/450 < b.l/450;
	return a.r/450 < b.r/450;
}


/*
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:66:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   66 |  for(register int i = 1; i <= n; ++i){
      |                   ^
index.cpp:69:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   69 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:74:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   74 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:90:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   90 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:88:19: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |   ans[q[i].index] = best;
      |   ~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2528 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 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2528 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 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 178 ms 4948 KB Output is correct
12 Correct 181 ms 4972 KB Output is correct
13 Correct 184 ms 4988 KB Output is correct
14 Correct 176 ms 4980 KB Output is correct
15 Correct 183 ms 4944 KB Output is correct
16 Correct 178 ms 4944 KB Output is correct
17 Correct 175 ms 4948 KB Output is correct
18 Correct 179 ms 4972 KB Output is correct
19 Correct 176 ms 4980 KB Output is correct
20 Correct 180 ms 4944 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2528 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 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 178 ms 4948 KB Output is correct
12 Correct 181 ms 4972 KB Output is correct
13 Correct 184 ms 4988 KB Output is correct
14 Correct 176 ms 4980 KB Output is correct
15 Correct 183 ms 4944 KB Output is correct
16 Correct 178 ms 4944 KB Output is correct
17 Correct 175 ms 4948 KB Output is correct
18 Correct 179 ms 4972 KB Output is correct
19 Correct 176 ms 4980 KB Output is correct
20 Correct 180 ms 4944 KB Output is correct
21 Correct 1126 ms 6160 KB Output is correct
22 Correct 1110 ms 9912 KB Output is correct
23 Correct 1130 ms 9980 KB Output is correct
24 Correct 1136 ms 9852 KB Output is correct
25 Correct 1129 ms 9852 KB Output is correct
26 Correct 1118 ms 10064 KB Output is correct
27 Correct 1151 ms 9860 KB Output is correct
28 Correct 1111 ms 9852 KB Output is correct
29 Correct 1115 ms 10068 KB Output is correct
30 Correct 1114 ms 9852 KB Output is correct