Submission #923604

#	Time	Username	Problem	Language	Result	Execution time	Memory
923604		Isam	Index (COCI21_index)	C++17	20 / 110	2538 ms	5468 KiB

index

#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 = 200001;

int n, Q, c[sz], tree[sz << 2], 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);
	update(l, mid, node << 1, x, val);
	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 (stderr)

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

• Subtask 1: 20 / 20
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50