Submission #1171406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171406		uranhishig	Index (COCI21_index)	C++20	0 / 110	2 ms	320 KiB

index

// Mo's algorithm
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ss second

const int N = 8e6 + 5;
int bit[N];
int a[N];

void update (int idx, int val) {
	while(idx < N) {	
		bit[idx] += val;	
		idx += idx & -idx;	
	}
}
int get (int idx) {
	if (idx<=0) {
		return 0;
	}
	int s = 0;
	while (idx > 0){
		s += bit[idx];
		idx -= idx & -idx;
	}
	return s;
}
signed main() {
	int n, q;	
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		update(i, a[i]);
	}
	while (q--) {
		int l, r;	cin >> l >> r;
		int L = l;
		int R = r;
		while (L + 1 < R) {
			int mid = (L + R + 1) / 2;
			if ( get(mid) - get(L - 1) > mid ) {
				L = mid;
			}
			else {
				R = mid;
			}
		}
		cout << "* "<< L << endl;
	}
	return 0;
}

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