oj.uz

Submission #923648

# Submission time Handle Problem Language Result Execution time Memory
923648 2024-02-07T14:14:32 Z Isam Index (COCI21_index) C++17
60 / 110
 2500 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*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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 3 ms 2392 KB Output is correct
9 Correct 3 ms 2552 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 3 ms 2392 KB Output is correct
9 Correct 3 ms 2552 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 1293 ms 4656 KB Output is correct
12 Correct 1349 ms 5984 KB Output is correct
13 Correct 1347 ms 5984 KB Output is correct
14 Correct 1251 ms 5984 KB Output is correct
15 Correct 1368 ms 4692 KB Output is correct
16 Correct 1327 ms 5980 KB Output is correct
17 Correct 1315 ms 5984 KB Output is correct
18 Correct 1309 ms 4648 KB Output is correct
19 Correct 1286 ms 5980 KB Output is correct
20 Correct 1248 ms 6228 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 3 ms 2392 KB Output is correct
9 Correct 3 ms 2552 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 1293 ms 4656 KB Output is correct
12 Correct 1349 ms 5984 KB Output is correct
13 Correct 1347 ms 5984 KB Output is correct
14 Correct 1251 ms 5984 KB Output is correct
15 Correct 1368 ms 4692 KB Output is correct
16 Correct 1327 ms 5980 KB Output is correct
17 Correct 1315 ms 5984 KB Output is correct
18 Correct 1309 ms 4648 KB Output is correct
19 Correct 1286 ms 5980 KB Output is correct
20 Correct 1248 ms 6228 KB Output is correct
21 Execution timed out 2555 ms 10068 KB Time limit exceeded
22 Halted 0 ms 0 KB -