제출 #1278634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278634		iagozag	Index (COCI21_index)	C++20	60 / 110	2542 ms	231024 KiB

index

#include <bits/stdc++.h>
using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define int ll

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

// SegTree Persistente com Lazy
//
// Nao propaga, meio estranho de mexer, mas da
//
// query(a, b, t) retorna a query de [a, b] na versao t
// update(a, b, x, t) faz um update v[a..b]+=x a partir da
// versao de t, criando uma nova versao e retornando seu id
// Por default, faz o update a partir da ultima versao
//
// build - O(n)
// query - O(log(n))
// update - O(log(n))

const int MAX = 2e5+10, UPD = 2e5+10, LOG = 19;
const int MAXS = 2*MAX + 4*UPD*LOG;

namespace perseg {
	int seg[MAXS], lazy[MAXS];
	int rt[UPD], L[MAXS], R[MAXS], cnt, t;
	int n, *v;

	int build(int p, int l, int r) {
		if (l == r) return seg[p] = v[l];
		L[p] = cnt++, R[p] = cnt++;
		int m = (l+r)/2;
		return seg[p] = max(build(L[p], l, m), build(R[p], m+1, r));
	}
	void build(int n2, int *v2) {
		n = n2, v = v2;
		rt[0] = cnt++;
		build(0, 0, n-1);
	}
	int query(int a, int b, int p, int l, int r) {
		if (b < l or r < a) return -INF;
		if (a <= l and r <= b) return lazy[p] + seg[p];
		int m = (l+r)/2;
		int ret = lazy[p] + max(query(a, b, L[p], l, m), query(a, b, R[p], m+1, r));
		return ret;
	}
	int query(int a, int b, int tt) {
		return query(a, b, rt[tt], 0, n-1);
	}
	int update(int a, int b, int x, int lp, int p, int l, int r) {
		tie(seg[p], lazy[p], L[p], R[p]) = {seg[lp], lazy[lp], L[lp], R[lp]};
		if (b < l or r < a) return seg[p] + lazy[p];
		if (a <= l and r <= b) return seg[p] + (lazy[p] += x);

		int m = (l+r)/2;
		seg[p] = max(update(a, b, x, L[lp], L[p] = cnt++, l, m),
					 update(a, b, x, R[lp], R[p] = cnt++, m+1, r));
		lazy[p] = lazy[lp];
		return seg[p] + lazy[p];
	}
	int update(int a, int b, int x, int tt=t) {
		assert(tt <= t);
		update(a, b, x, rt[tt], rt[++t]=cnt++, 0, n-1);
		return t;
	}
};

void solve(){
	int n, q; cin >> n >> q;
	vector<int> v(n); for(int i = 0; i < n; i++) cin >> v[i];

	int hist[MAX] = {0};
	perseg::build(MAX, hist);

	for(int i = 0; i < n; i++)
		perseg::update(0, v[i], 1);

	for(int i = 0; i < q; i++){
		int a, b; cin >> a >> b; --a;
		
		int l = 1, r = MAX, ans = l;
		while(l <= r){
			int m = l+(r-l)/2;
			if(perseg::query(m, m, b)-perseg::query(m, m, a) >= m) ans = m, l = m+1;
			else r = m-1;
		}

		cout << ans << endl;
	}
}

int32_t main(){ _
    int ttt = 1; // cin >> ttt;

    while(ttt--) solve();

    exit(0);
}

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