Submission #894311

#	Time	Username	Problem	Language	Result	Execution time	Memory
894311		vjudge1	Index (COCI21_index)	C++17	110 / 110	1536 ms	14800 KiB

index

#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 2e5 + 2;
const int M = 7e6 + 1;
int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 31;

int mult(int a, int b) {
    return a * 1LL * b % mod;
}

int sum(int a, int b) {
    a %= mod; 
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}

ll binpow(ll a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}

struct fenwick{
    int bt[N];

    fenwick(){
        memset(bt, 0, sizeof bt);
    }

    void add(int i, int x){
        for(; i < N; i = (i | (i + 1)))
            bt[i] += x;
    }

    int get(int r){
        int ret = 0;
        for(; r >= 0; r = ((r & (r + 1)) - 1)){
            ret += bt[r];
        }
        return ret;
    }

    int get(int l, int r){
        return get(r) - get(l - 1);
    }
} f;

int block = 500;

bool cmp(pair<pii, int> a, pair<pii, int> b){
    if(a.F.F / block == b.F.F / block)
        return a.F.S < b.F.S;
    return ((a.F.F / block) < (b.F.F / block));
}

void del(int x){
    f.add(x, -1);
}

void add(int x){
    f.add(x, 1);
}

int geta(){
    int lo = 0, hi = N;
    while(lo + 1 < hi){
        int m = (lo + hi) / 2;
        if(m <= (f.get(m, N - 1)))
            lo = m;
        else
            hi = m;
    }
    return lo;
}

void solve(){
    int n, q;
    cin >> n >> q;
    int p[n + 1];
    for(int i = 1; i <= n; i++)
        cin >> p[i];
    vector<pair<pii, int>> qs(q);
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        qs[i] = {{l, r}, i};
    }
    int ans[q];
    sort(all(qs), cmp);
    int cl = 1, cr = 0;
    for(auto e : qs){
        int l = e.F.F, r = e.F.S, ind = e.S;
        while(cl > l){
            cl--;
            add(p[cl]);
        }
        while(cr < r){
            cr++;
            add(p[cr]);
        }
        while(cl < l){
            del(p[cl]);
            cl++;
        }
        while(cr > r){
            del(p[cr]);
            cr--;
        }
        ans[ind] = geta();
    }
    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}   

signed main() {
    //mispertion;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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