oj.uz

Submission #894311

# Submission time Handle Problem Language Result Execution time Memory
894311 2023-12-28T04:45:19 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 1536 ms 14800 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 = 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.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 2 ms 1880 KB Output is correct
3 Correct 2 ms 1884 KB Output is correct
4 Correct 2 ms 1884 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 2 ms 1884 KB Output is correct
7 Correct 2 ms 1884 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 3 ms 1880 KB Output is correct
10 Correct 2 ms 1884 KB Output is correct
11 Correct 319 ms 4204 KB Output is correct
12 Correct 314 ms 4180 KB Output is correct
13 Correct 316 ms 4176 KB Output is correct
14 Correct 312 ms 4180 KB Output is correct
15 Correct 309 ms 4436 KB Output is correct
16 Correct 312 ms 4200 KB Output is correct
17 Correct 310 ms 4436 KB Output is correct
18 Correct 319 ms 4204 KB Output is correct
19 Correct 311 ms 4432 KB Output is correct
20 Correct 326 ms 4176 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 2 ms 1880 KB Output is correct
3 Correct 2 ms 1884 KB Output is correct
4 Correct 2 ms 1884 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 2 ms 1884 KB Output is correct
7 Correct 2 ms 1884 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 3 ms 1880 KB Output is correct
10 Correct 2 ms 1884 KB Output is correct
11 Correct 319 ms 4204 KB Output is correct
12 Correct 314 ms 4180 KB Output is correct
13 Correct 316 ms 4176 KB Output is correct
14 Correct 312 ms 4180 KB Output is correct
15 Correct 309 ms 4436 KB Output is correct
16 Correct 312 ms 4200 KB Output is correct
17 Correct 310 ms 4436 KB Output is correct
18 Correct 319 ms 4204 KB Output is correct
19 Correct 311 ms 4432 KB Output is correct
20 Correct 326 ms 4176 KB Output is correct
21 Correct 1513 ms 10836 KB Output is correct
22 Correct 1524 ms 14676 KB Output is correct
23 Correct 1536 ms 14544 KB Output is correct
24 Correct 1527 ms 14540 KB Output is correct
25 Correct 1520 ms 14800 KB Output is correct
26 Correct 1517 ms 14540 KB Output is correct
27 Correct 1447 ms 14540 KB Output is correct
28 Correct 1507 ms 14544 KB Output is correct
29 Correct 1513 ms 14544 KB Output is correct
30 Correct 1511 ms 14548 KB Output is correct