oj.uz

Submission #923617

# Submission time Handle Problem Language Result Execution time Memory
923617 2024-02-07T13:39:28 Z Isam Index (COCI21_index) C++17
60 / 110
 945 ms 2388 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 = 60000;

int n, Q, c[sz], tree[sz*3], 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;
}



inline void update(int l, int r, int node, int x, int val){
	if(l > r || l > x || r < x) return;
	if(l == r){
		tree[node] += val;
		return;
	}
	int mid = l + ((r  - l) >> 1);
	if(x <= mid) update(l, mid, node << 1, x, val);
	else update(mid + 1, r, node << 1 | 1, x, val);
	tree[node] = tree[node << 1] + tree[node << 1 | 1];
	return;
}




int get(int l, int r, int node, int L, int R){
	if(l > r || l > R || r < L) return 0;
	if(l >= L && r <= R) return tree[node];
	int mid = l + ((r - l) >> 1);
	return get(l, mid, node << 1, L, R) + get(mid + 1, r, node << 1 | 1, L, R);
}

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

inline void del(int x){
	update(1, n, 1, 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(1, n, 1, 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:60:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   60 |  for(register int i = 1; i <= n; ++i){
      |                   ^
index.cpp:63:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   63 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:68:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   68 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:84:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   84 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:82:19: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |   ans[q[i].index] = best;
      |   ~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 508 KB Output is correct
6 Correct 3 ms 500 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 4 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 508 KB Output is correct
6 Correct 3 ms 500 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 945 ms 2128 KB Output is correct
12 Correct 873 ms 2384 KB Output is correct
13 Correct 904 ms 2388 KB Output is correct
14 Correct 890 ms 2192 KB Output is correct
15 Correct 877 ms 2132 KB Output is correct
16 Correct 891 ms 2388 KB Output is correct
17 Correct 882 ms 2192 KB Output is correct
18 Correct 876 ms 2196 KB Output is correct
19 Correct 883 ms 2192 KB Output is correct
20 Correct 926 ms 2188 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 508 KB Output is correct
6 Correct 3 ms 500 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 945 ms 2128 KB Output is correct
12 Correct 873 ms 2384 KB Output is correct
13 Correct 904 ms 2388 KB Output is correct
14 Correct 890 ms 2192 KB Output is correct
15 Correct 877 ms 2132 KB Output is correct
16 Correct 891 ms 2388 KB Output is correct
17 Correct 882 ms 2192 KB Output is correct
18 Correct 876 ms 2196 KB Output is correct
19 Correct 883 ms 2192 KB Output is correct
20 Correct 926 ms 2188 KB Output is correct
21 Runtime error 5 ms 856 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -