oj.uz

답안 #715122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715122 2023-03-25T23:26:53 Z TheConverseEngineer Index (COCI21_index) C++17
0 / 110
 3 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define sqr(x) ((ll)(x))*(x)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct MergeSortTree {
	vector<vi> s;
	void buildFullTree() {
		for (int i = sz(s)/2-1; i > 0; i--) { 
			s[i].resize(sz(s[i<<1]) + sz(s[i<<1|1]));
			merge(all(s[i<<1]), all(s[i<<1|1]), s[i].begin());
		}
	}
	int countGreater(int l, int r, int k) { 
		int output = 0;
		for (l += sz(s)/2, r += sz(s)/2; l < r; l /= 2, r /= 2) {
			if (l&1) output += s[l].end() - upper_bound(all(s[l]), k), l++;
			if (r&1) --r, output += s[r].end() - upper_bound(all(s[r]), k);
		}
		return output;
	}
};

int N, Q;
MergeSortTree tree;


int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> Q; tree.s.resize(2*N, vi(0));
	FOR(i, 0, N) {
		int a; cin >> a; tree.s[N+i] = {a};
	}
	tree.buildFullTree();

	FOR(query, 0, Q) {
		int l, r; cin >> l >> r;
		int works = -1;
		for (int move = r-l+1; move > 0; move /= 2) {
			if (tree.countGreater(l-1, r, works+move-1) >= works+move) works += move;
		}
		cout << works << "\n";
	}
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -