Submission #1286059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286059		vieiras	Index (COCI21_index)	C++20	110 / 110	1654 ms	112440 KiB

index

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

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define pb push_back
#define f first
#define s second
#define int long long
typedef pair<int, int>ii;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;

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

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

	ll 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] = 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);
	}
	ll query(int a, int b, int p, int l, int r) {
		if (b < l or r < a) return 0;
		if (a <= l and r <= b) return seg[p];
		int m = (l+r)/2;
		return query(a, b, L[p], l, m) + query(a, b, R[p], m+1, r);
	}
	ll query(int a, int b, int tt=t) {
		return query(a, b, rt[tt], 0, n-1);
	}
	ll update(int a, int x, int lp, int p, int l, int r) {
		if (l == r) return seg[p] = seg[lp]+x;
		int m = (l+r)/2;
		if (a <= m)
			return seg[p] = update(a, x, L[lp], L[p]=cnt++, l, m) + seg[R[p]=R[lp]];
		return seg[p] = seg[L[p]=L[lp]] + update(a, x, R[lp], R[p]=cnt++, m+1, r);
	}
	int update(int a, int x, int tt=t) {
		update(a, x, rt[tt], rt[++t]=cnt++, 0, n-1);
		return t;
	}
};


int n, q;

int32_t main(){_
    cin >> n >> q;

    //guarda o tempo de quanto o vetor passou a ter todos os artigos com indice pelo menos k.
    int tms[maxn];
    int auxv[maxn];
    memset(auxv, 0, sizeof auxv);
    perseg::build(maxn, auxv);
    vector<int> vals[maxn];
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        vals[a].pb(i);
    }
    
    int last = 0;
    for(int i = maxn-1; i >= 0; i--){
        while(vals[i].size()){
            int va = vals[i].back();
            vals[i].pop_back();
            last = perseg::update(va, 1);
        }
        tms[i] = last;
    }

    while(q--){
        int a, b; cin >> a >> b;
        a--;
        b--;
        //cout << perseg::query(a, b, tms[4]) << endl;
        int l = 0, r = 200000;
        while(l<r){
            int m = (l+r+1)/2;
            if(perseg::query(a, b, tms[m]) >= m) l = m;
            else r = m-1;
        }
        cout << l <<endl;
    }
}

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