oj.uz

Submission #894310

# Submission time Handle Problem Language Result Execution time Memory
894310 2023-12-28T04:45:06 Z vjudge1 Index (COCI21_index) C++17
20 / 110
 61 ms 2428 KB 
#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 = 5e3 + 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 61 ms 2428 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 61 ms 2428 KB Output isn't correct
12 Halted 0 ms 0 KB -