oj.uz

Submission #923625

# Submission time Handle Problem Language Result Execution time Memory
923625 2024-02-07T13:45:14 Z Isam Index (COCI21_index) C++17
20 / 110
 2500 ms 1872 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 != b.l) return a.l < b.l;
	return a.r < b.r;
}



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 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 600 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Execution timed out 2532 ms 1872 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Execution timed out 2532 ms 1872 KB Time limit exceeded
12 Halted 0 ms 0 KB -