Submission #923648

#	Time	Username	Problem	Language	Result	Execution time	Memory
923648		Isam	Index (COCI21_index)	C++17	60 / 110	2555 ms	10068 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 = 200005;

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/600 != b.l/600) return a.l/600 < b.l/600;
	return a.r/600 < b.r/600;
}


/*
1 1000

300 500

1) 1000 + 800 = 1800


2) 500 + 800 = 1300

*/



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 (stderr)

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

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